CareerCup

I am pretty sure that following soln will work. The concept is simple, if at any point we find that the current petrol used is less than the distance traveled then just start again from the very next point considering it as the first point.

public int petrolPump(int[] petrol, int[] distance){
	int i = 0, start = 0, tot = 0;
	while(true){
		tot++;
		if(count == 0){
			start = i;
                
                }
		cp = cp + petrol[i];
		dist = dist + distance[i];
		count++;
		if(cp < dist){
			count = 0;
			cp=0;
			dist = 0;
		}

		if(count == len)
			break;
		i++;
		if(i>len-1)
			i = 0;
		if(tot >= 2*len)
			return -1;

	}

	return start;

}

my algorithm is similar to most of the algorithms explained above but, it uses O(1) of extra space;

basic idea is that if we start at any point then in order to reach back at that point is possible
if and only if the minimum cumulative sum of the differences of dist[i]-petrol[i] from the starting point to the last point in the circle should be non-negative, and this can be managed in O(1) space very easily.....:)

@msramachandran
We can compute the sum of distance in linear time:
first we concatenate the distance vector with itself to get a int dist[2n]
to compute the sum of n consecutive numbers, do the following:
for the first n numbers, just add them one by one, then we get sum[n],
then for sum[n+i] compute it this way:
sum[n+i]=sum[n]-dist[i],
then we get all sums, just pick the first sum that is >0.

I think the O(n) space is not necessary, the following code should work:

public static void main(String[] args) {
		
		int[] petrol = {3,5,6};
		int[] dist= {2,7,3};
		int sum = 0;
		int startPoint = -1;
		for (int i=0;i< petrol.length;i++){
			sum +=(petrol[i]-dist[i]);
			if (sum < 0){
				startPoint = -1;
			}else if (startPoint == -1){
				startPoint = i;
			}
		}
		if (startPoint == -1){
			System.out.println("Can not find");	
		}else{
			System.out.println("found start point:" + startPoint);
		}
	}

let petrol[i] and dist[i] be the two respective arrays.

make a new array arr[i] = petrol[i] - dist[i];

find the maximal sub-sequence in this arr. the beginning of this maximal sub sequence would be the starting point of the travel.

@msramachandran

I thought of the same thing but here's a counter example.

-12 10 10

You'll need to start from the first 10 but the sequential sum of the difference array would be,

-12 -2 8 and it would suggest starting from the second 10.

How about this?
suppose i is the first point, and that the truck can travel to point j but can't travel to j+1. so the truck can not travel to j+1 if it starts any point between i and j.

Hi

Assume diff[i] = petrol[i] - dist[i]
Concatenate diff array so that we have diff[i + N] = diff[i]

Then use the following modification max sum sub-sequence algorithm

int maxsofar = 0, count = 0;
for (i = 0 ; i < 2N ; i++) {
maxsofar += diff[i];
if (maxsofar < 0) {
/** petrol is less than the distance **/
maxsofar = 0;
count = 0;
} else {
/** petrol is more than distance - increment petrol pump **/
count++;
if (count == N) {
/** we have visited N pumps - success **/
printf("The first petrol pump to start is %d", i - N + 1);
break;
}
}
}

O(N) extra space for diff array and O(N) runtime.

how to approach such problem : ?

observations needed

a car can only start and reach at the same point back only and only if it has non negative petrol all the time.

it has infinite capacity so it will take all the petrol that is available to it .

mileage is 1km/ltr which just simplifies the calculation . the amount of petrol in car is equal to the distance it can travel.

line of thought : let car start from any petrol pump and reach the next petrol pump and fill its tank . at this point the car will contain residual petrol from the previous petrol pump and full petrol of current petrol pump. this will keep on happening till it reaches the same petrol pump again or petrol in tank becomes negative.



now let petrol pum capacity = [1, 1, 2, 3 , 1]

and distance between pumps =[2, 1, 1, 1, 3 ]

let there be another array diff=[-1, 0, 1, 2, -2] the difference between 1st and 2nd array { it was allowed to use O(n) space so it was hint that helper array can be used }

if car starts from i-th petrol pump and is currently at j-th petrol pump .. petrol in its tank will be the sum of elements of diff array from i to j . so car will be able to reach its origin point only when the sum of elements from its start point i and end point j ( the last petrol pump) is at least zero.

in this example truck can start from both B and C of petrol pump { A,B,C,D,E

python code based on above

fuel = map(lambda x:int(x), raw_input().split())
distance = map(lambda x:int(x), raw_input().split())

# takes the standard input as space separated integers in two lines.

diff = [b-a for b,a in zip(fuel, distance)] # creates the diff array
diff = diff + diff  # to account for cyclic array

start = 0 # let say we start from 0 the position
end = 0
summation = 0
counter = 0 # keeps the count of petrol pumps accessed
for i in range(len(diff)):
    if(end - start >= len(distance)):
        break; 
    summation += diff[i]
    end += 1
    if(summation < 0):
        summation = 0
        start +=1
        end = start

if(end - start == len(distance)): # we covered exactly 5 petrol pumps
    print start
else:
    print "solution doesn't exist"

Simple and elegant solution to this problem is:

///Stations are starting from index 0 to n-1.
#include<iostream>
using namespace std;
struct petrolPump
{
	int petrol;
	int nxtDistance;
};
int main()
{
	int n;
	cout<<"\n Enter the total number of pumps: ";
	cin>>n;
	struct petrolPump p[n];
	for(int i=0;i<n;i++)
	{
		cout<<"\n Enter the petrol Capacity : ";
		cin>>p[i].petrol;
		cout<<"\n Enter the next distance :";
		cin>>p[i].nxtDistance;
	}
	// Elimination of starting point
	int start =0;
	int i=0;
	while(p[i].petrol<p[i].nxtDistance)
	{
	i++;
	start++;
}
	int loopIndicator = start;
	int end= start;
	int leftPetrol=0;
	while(1)
	{
		leftPetrol = leftPetrol-p[start].nxtDistance+p[start].petrol;
	
		if(leftPetrol<0)
		{
			loopIndicator++;
			//cout<<loopIndicator<<" ";
			start = loopIndicator;
			cout<<"\n Not possible with this start station. So changing the start station to "<<start<<endl;
			leftPetrol = 0;
			continue;
		}
		start= (++start)%n;
		cout<<"\n Vechile is now at station "<<start<<" with leftOver petrol : "<<leftPetrol<<endl;
		if(start==loopIndicator)
		break;
		
	}
	if(start==loopIndicator)
	{
		cout<<"\nStart Station is "<<start<<endl;
	}
	
	
	return 0;
}