Gardener's Steps Along the Beds

Medium

Garden beds numbered 0 to n - 1 stand in a row along a path; bed i is at point x = i. At point x = -1 there is a well where the gardener fills a watering can that holds can_size units. One step moves one unit along the path. Bed i needs exactly needs[i] units of water. The gardener starts at the well with a full can and waters the beds strictly from left to right. If, after finishing a bed, the can does not hold enough to fully water the next one, the gardener walks back to the well, fills the can to the brim and walks back. Refilling early is not allowed. Return the total number of steps needed to water every bed.

Example 1

needs=[3, 1, 4, 2], can_size=5 → 14

1 step to bed 0 (2 units left), 1 step to bed 1 (1 left). Bed 2 needs more: 2 steps back to the well and 3 steps out (1 left). Bed 3 needs more again: 3 steps back and 4 out. Total 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2

needs=[2, 2, 2], can_size=6 → 3

One full can covers every bed, so it is just 3 steps.

Example 3

needs=[4, 4, 4], can_size=4 → 9

Constraints

n = len(needs)
1 ≤ n ≤ 1000
1 ≤ needs[i] ≤ 10⁶
max(needs) ≤ can_size ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Simulation