Circular Tour
You have been given a circular path. There are N petrol pumps on this path that are numbered from 0 to N - 1 (Both inclusive). Each petrol pump has two values associated with it:

1)The amount of petrol that is available at this particular petrol pump.

2)The distance to reach the next petrol pump.

You are on a truck having an empty tank of infinite capacity. You can start the tour from any of the petrol pumps. Your task is to calculate the first petrol pump from where the truck will be able to complete the full circle or determine if it is impossible to do so.

You may assume that the truck will stop at every petrol pump and it will add the petrol from that pump to its tank. The truck will move one kilometre for each litre of petrol consumed.

Input Format

The first line of input contains an integer 'N' representing the number of petrol pumps. Each of the next N lines will contain a pair of space-separated integers representing the amount of petrol that pump has and the distance to reach the next petrol pump, respectively.

Output Format :

Print an integer representing the index of the first petrol pump from which we should start the tour. If no such petrol pump exists, print ‘-1’.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function. Make sure that the output has 0 - based indexing.

Constraints:

1

Question

Circular Tour

You have been given a circular path. There are N petrol pumps on this path that are numbered from 0 to N - 1 (Both inclusive). Each petrol pump has two values associated with it:

1)The amount of petrol that is available at this particular petrol pump.

2)The distance to reach the next petrol pump.

You are on a truck having an empty tank of infinite capacity. You can start the tour from any of the petrol pumps. Your task is to calculate the first petrol pump from where the truck will be able to complete the full circle or determine if it is impossible to do so.

You may assume that the truck will stop at every petrol pump and it will add the petrol from that pump to its tank. The truck will move one kilometre for each litre of petrol consumed.

Input Format

The first line of input contains an integer 'N' representing the number of petrol pumps.

Each of the next N lines will contain a pair of space-separated integers representing the amount of petrol that pump has and the distance to reach the next petrol pump, respectively.

Output Format :

Print an integer representing the index of the first petrol pump from which we should start the tour. If no such petrol pump exists, print ‘-1’.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.  Make sure that the output has 0 - based indexing.

Constraints:

1 <= N <= 5*10^5
1 <= Amount of petrol on each pump <= 10^9
1 <= Distance to next pump <= 10^9

Where N is the total number of petrol pumps on the circular path.

Time Limit: 1sec

Accepted Answer

Explanation : Let's take an example

Petrol_Pump = [1, 2, 3, 4, 5]

Distance = [3, 4, 5, 1, 2]

ind = [0, 1, 2, 3, 4]

Now we will find difference the betweeen Petrol_Pump[i] - Distance[i] = [-2, -2, -2, 3, 3] ===> (sum of all values) ==>0 and if it means solution is exists or else we will return -1

lets take tank as a capacity for storing water as a 0.
if i = 0, index = 0 at that time we will do tank += Petrol_Pump[i] - Distance[i]

if(tank < 0) it means we can't get the result for previous indexes, So we will update to i+1

And at last we will check if total < 0 we will return -1 else we will return our updated index.

So, we calculate the consumption of travel from one Petrol_Pump station to other. If the fuel in tank is less than 0, then reset to zero, because the Petrol_Pump as start cannot support the problem. So, change the start index. And also, calculate the total consumption, so that no need of iteration in clockwise is needed. If total is still negative, then no answer

Accepted Answer

Brute Force

We can choose every index to be our starting point and check whether we can complete the round trip starting from that index.
For each start point, we will run a loop starting from this index. If at any point, petrol available in the truck is not sufficient to move on to the next petrol pump, we know this is a bad starting point. So, we break the loop and try the same for the next start point.
As soon as we find a start point which results in a complete tour of all pumps, we return its index.
If no such index exists we will simply return -1.

Space Complexity: O(1)Explanation:

O(1), constant space is used.

Time Complexity: O(1)Explanation:

O(N^2), where N denotes the total number of petrol stations.

As every petrol pump will be visited at most N times (for each of the N starting points), the time complexity will be O(N^2).

Accepted Answer

Array Sum

Condition for -1, i.e. No trip is possible:
- If the total distance that we have to travel is strictly greater than the total petrol available to us, then no matter what starting index we choose, we will not be able to complete our trip.
- So we will find the summation of total petrol available and the total distance we have to travel and check if the former is greater or equal to the latter.

We will start travelling from the petrol pump situated at index 0.

We will maintain a variable ‘sum’ (with an initial value equal to zero) which stores the difference between total petrol used and total distance travelled till a particular index starting from index 0.

The index where the variable sum has the least value will be our answer because
- If the value of sum remains non-negative throughout the iteration, then index 0 will be our answer.
- The index where the value of sum is least (and it will be negative), let that index be y. Then y, cannot be reached starting from index (0,1,2,..., y-1).
- Hence it is optimal to make y as our starting point as there is at least one answer possible.
- In case there are several indexes with the minimum value, the lowest index will be our answer.