Been looking at more interview problems and such, and was thinking about this problem for too long.
Suppose you have a car with no gas on a circular road.
Given two lists of integers corresponding to costs $\{c_i \}_{i=1}^n$ and gasoline $\{g_i \}_{i=1}^n$ with the $i$th index corresponding to the amount of gasoline, and it takes the $i$th cost to reach the next gasoline tank.
If $\sum_i g_i \ge \sum_i c_i$, is it always possible to go around the circle?
Approach one: induction:
The base case of 1 is too trivial to mention, as the “next gas station” is itself. So consider the base case of 2, where one gas station will always have enough to reach the next gas station. Then, by the inequality, we have our lap.
As for the inductive step, we just need to reduce the $n+1$ gas/cost into $n$. This is actually quite easy: there must exist a single gas/cost index such that it can reach the next one (if not, then the assumed inequality is false). Combine that index and the next index as one super node by summing, and we are done.
Approach two: extremal principle:
This is a bit more technical; we consider the partial sums $S_k = \sum_{i=1}^k (g_i – c_i)$.
By assumption, $S_n \ge 0$ and we simply seek a rotation such that $S_k \ge 0$ for all $k$. Suppose that we do not have this, and let $m$ be such that $S_m$ is minimal. In particular, $S_m < 0$. Now consider the following "rotation": we start at $m+1$. This results in the new partial sums being $T_k = S_{m+1+k} - S_m$. Since it's just shifting by $S_m$, which is strictly more negative than all other $S_k$, then $T_k$ is strictly nonnegative.