Monday, July 18, 2016

circular tour

Given gas stations with gas at each gas station and distance between them, return any gas station starting from which a loop exists. All gas stations need to be visited, in order, only once.

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
    distance
// time O(n), O(1) space
(points):
    looppoint = null
    sum = 0
    for point in points:
        delta = point.gas - (point.distance / mpg)
        sum += delta
        if sum >= 0:
            if looppoint == null:
                looppoint = point
        else:
            looppoint = null
    return looppoint
[Hat tip to B]

Another logic that works is this. The loop point is the next point when the sum is least if sum >= 0 in end.
(points):
    loopi = 0
    sum = 0
    minsum = 0
    for i, point in points:
        delta = point.gas - (point.distance / mpg)
        sum += delta
        if sum < minsum:
            minsum = sum
            loopi = i+1
    if sum < 0:
        loopi = -1
    looppoint = 0 <= loopi < points.length() ? points[loopi] : null
    return looppoint

No comments:

Post a Comment