You have a truck moving around a circular track with gas stations spaced out around the circle. Each station has a finite amount of gas. The gas tank on the truck is infinitely big. The distance between the gas stations requires a certain amount of gas to traverse. You can only move in one direction.
What is the algorithm to use? Which gas station do you start at? Can you get all the way around and back to the start station?
Yes O(n) is possible. Definitely not TSP.
Let xi be the amount of gas available at station i minus the amount of gas required to go to next station.
A requirement is Σ xi ≥ 0 (enough gas to complete a full circle).
Consider Si = x1 + x2 + ... + xi
Note that Sn ≥ 0.
Now pick the smallest (or even largest will do, making it easier to write code for) k such that Sk is the least and start at the station next to it.
Now for k < j ≤ n, we have the gas in tank = Sj - Sk ≥ 0.
for 1 ≤ j ≤ k, we have gas in tank = xk+1 + .. + xn + x1 + x2 + .. + xj = Sn - Sk + Sj ≥ 0.
Thus starting at k+1 will ensure there is enough gas accumulated at each station to get to the next station.
// C++ code. gas[i] is the gas at station i, cost[i] is the cost from station i to (i+1)%n
int circ(vector<int> &gas, vector<int> &cost) {
int min_S=INT_MAX, S=0, position=0;
for(int i=0;i<gas.size();i++)
{
S += gas[i] - cost[i];
if(S<min_S)
{
min_S = S;
position = (i+1) % gas.size();
}
}
if(S>=0)
return position;
else
return -1;
}
We are given with 2 arrays, one for amount of gas available at bunk Bi and one for the amount of gas we spend to reach from i to i+1. We try to start from the first bunker and assume it to be the solution. When even we see that residue gas + available gas at bunker is < amount of gas required we reset the solution to the next index repeat the process till we reach the starting point(our last assumed solution)
public int getStationIndex() {
int answer = -1;
if (gasAvailableArray.length != gasExpenditureArray.length) {
throw new IllegalArgumentException("Invalid input array provided");
}
Queue<Integer> queue = new ArrayDeque<>();
int residue = 0;
for (int index = 0; ; ) {
if (index >= gasAvailableArray.length) {
index = index % (gasAvailableArray.length - 1);
}
if (index == answer) {
return answer;
}
if (residue + gasAvailableArray[index] - gasExpenditureArray[index] >= 0) {
// Only set a new answer when we had a reset in last iteration
if (answer == -1) {
answer = index;
}
residue += gasAvailableArray[index] - gasExpenditureArray[index];
queue.add(index);
} else {
while (!queue.isEmpty()) {
queue.poll();
}
}
answer = -1;
index++;
}
}
static int findIndex(int A[], int B[]) {
int N = A.length;
int start=0;
boolean isBreak=false;
int total = 0;
do {
for(int i=start;i<start+A.length;i++) {
int c = A[i%N] - B[i%N];
total +=c;
if(total < 0) {
total= 0;
isBreak=true;
break;
}
}
if(isBreak) {
start++;
isBreak=false;
} else {
return start;
}
} while(start < A.length);
return -1;
}
static int find(int A[], int B[]) {
for (int start = 0; start < A.length; start++) {
int x = findIndex(A, B, start);
if (x != -1)
return x;
}
return -1;
}
static int findIndex(int A[], int B[], int start) {
int total=0;
int N = A.length;
for (int i = start; i < start + A.length; i++) {
int c = A[i % N] - B[i % N];
total += c;
if (total < 0) {
total = 0;
return -1;
}
}
return start;
}
Test cases:
A : { 1, 2, 3, 4, 5 }, B : { 1, 3, 2, 4, 5 } --> index 2A : {2,2,1}, B : {2,1,2} index --> 0A : {1,2}, B {2,1} --> index 1 A : {1,2,1}, B {2,1,3} --> index -1static int getIndex(int A[], int B[]) {
int start = -1;
int N = A.length;
for (int i = 0; i < N; i++) {
int c = A[i] - B[i];
if (c >= 0) {
int j = i + 1;
while (c >= 0 && j < i + N) {
c += A[j % N] - B[j % N];
j++;
}
if (c >= 0) {
start = i;
break;
}
}
}
return start;
}