Problem

Submissions

Hints & solutions

Discuss

Gas Stations

Moderate

0/80

Average time to solve is 10m

Contributed by

21 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case 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:

For each test case, print a single line containing a single integer representing the index of the first petrol pump from which we should start the tour. If no such petrol pump exists, print ‘-1’.

The output for each test case will be printed in a separate line.

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 <= T <= 50
1 <= N <= 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.

Sample Input 1 :

Sample Output 1 :

1
0

Explanation for Sample 1 :

In the first test case, if we start from the petrol pump at index 0, we will not be able to travel to index one as petrol available for travelling is less than the distance.
If we start at index 1, we can complete our journey (1 -> 2 -> 0 -> 1) easily.

In the second test case, we can start our journey from the petrol pump at index 0 and complete the journey.

Sample Input 2 :

Sample Output 2 :

-1

Explanation for Sample 2 :

We will not be able to visit every petrol pump from any index.

Hint 1

Hint 2

Can you think about trying every possible petrol pump as the starting pump?

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

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).

Space Complexity

O(1).

We are using constant space.

(100% EXP penalty)

Gas Stations

Console