#183MediumGreedy· Circular Route with Running Balance

Charging Station Loop

An electric bus runs a circular route with `n` stops, numbered `0` to `n - 1` in driving order, and after stop `n - 1` it returns to stop 0. At stop `i` a charger adds `energy[i]` units to the battery, and driving from stop `i` to the next stop uses `use[i]` units. The battery has unlimited capacity and starts empty; the bus charges at its first stop before driving, and must never run out of energy on the road (reaching a stop with exactly 0 left is fine). Return the **smallest** stop number from which the bus can complete one full lap and return to its starting stop, or `-1` if no stop works.

Input format

`energy`: an array of non-negative integers; `use`: an array of non-negative integers of the same length.

Output format

An integer: the smallest valid starting stop, or -1.

Examples

Input: energy = [1, 2, 3, 4, 5], use = [3, 4, 5, 1, 2]

Output: 3

Starting at stop 3 the battery runs 4 -> 3 -> 5 -> 3 -> ... and never goes negative over the lap, while starting at stops 0, 1 or 2 runs dry on the way.

Input: energy = [2, 3, 4], use = [3, 4, 3]

Output: -1

The total energy is 9 but the total consumption is 10, so no start can work.

Input: energy = [2, 2], use = [2, 2]

Output: 0

Both stops work; the smallest is 0.

Constraints

1 <= n <= 10^5
0 <= energy[i], use[i] <= 10^4
energy and use have the same length n.

Study first

Greedy Algorithms

#greedy
#arrays
#circular-array