Note:

- A loop exists if there is enough gas starting from any gas station. i.e. loop exists if total gas >= total distance (assume 1 mpg).

- If a loop exists clockwise for gas stations, it also does anti-clockwise. So direction does not matter.

We get this array with a surplus or deficit at each gas station.

- If sum >= 0 at the end, a loop exists. The loop gas station is the first one after which sum stays >= 0 till end. This logic does not work for all valid loop gas stations but works for at least one gas station if loop exists (see examples with -).

d: -1 4 -3 -1 1 s: -1 3 0 -1 0 - | d: -1 3 -4 0 1 s: -1 2 -2 -2 -1 // no loop d: -1 6 -3 -1 1 s: -1 5 2 1 2 | - d: -1 5 -7 4 2 -6 5 s: -1 4 -3 1 3 -3 2 - | point: gas distanceThe start is the first point where the surplus is >= 0 and stays so till the end.

point circularTour(points): loopstart = 0 surplus = 0 for i, point in points: surplus += point.gas - (point.distance / mpg) if surplus < 0: loopstart = i +1 if !(0 <= loopstart < points.length()): return null return points[loopstart]Without i.

point circularTour(points): loopstart = null surplus = 0 for point in points: loopstart = loopstart ?? point surplus += point.gas - (point.distance / mpg) if surplus < 0: loopstart = null return loopstart[Hat tip to B]

## No comments:

## Post a Comment