Gas Tank
You have a car with a gas tank of infinite capacity. There are ‘N’ gas stations along a circular route. Gas stations are numbered from 0 to N - 1. You begin the journey with an empty tank at one of the gas stations. You want to travel around the circular route once in the clockwise direction. I.e if you start to travel from station ‘i’, then you will go to i + 1, i + 2, …, n - 1, 0, 1, 2, i - 1 and then return back to ‘i’.

You are given two integer arrays ‘gas’ and ‘cost’. ‘gas[i]’ gives the amount of gas available at station ‘i’ and cost[i] gives the amount of gas required to travel from station ‘i’ to next station i.e station ‘i’+1 (or 0 if the station is N - 1).

Return the starting gas station's index if it is possible to complete cycle of given circular route once in the clockwise direction. If there are multiple possible starting gas station’s indexes, then return the minimum of those gas station indexes. If there is no such gas station then return -1.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run, then the T test cases follow. The first line of each test case contains a positive integer 'N' which represents the number of gas stations. The second line of each test case contains 'N' space-separated integers representing the integer array 'gas'. The third line of each test case contains 'N' space-separated integers representing the integer array 'cost'.

Output Format :

For each test case, print a single integer denoting the minimum index of the starting gas station if you are able to travel around the cycle once, otherwise print -1.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraint :

1

Question

Gas Tank

You have a car with a gas tank of infinite capacity. There are ‘N’ gas stations along a circular route. Gas stations are numbered from 0 to N - 1. You begin the journey with an empty tank at one of the gas stations. You want to travel around the circular route once in the clockwise direction. I.e if you start to travel from station ‘i’, then you will go to i + 1, i + 2, …, n - 1, 0, 1, 2, i - 1 and then return back to ‘i’.

You are given two integer arrays ‘gas’ and ‘cost’. ‘gas[i]’ gives the amount of gas available at station ‘i’ and cost[i] gives the amount of gas required to travel from station ‘i’ to next station i.e station ‘i’+1 (or 0 if the station is N - 1).

Return the starting gas station's index if it is possible to complete cycle of given circular route once in the clockwise direction. If there are multiple possible starting gas station’s indexes, then return the minimum of those gas station indexes. If there is no such gas station then return -1.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run, then the T test cases follow.

The first line of each test case contains a positive integer 'N' which represents the number of gas stations.

The second line of each test case contains 'N' space-separated integers representing the integer array 'gas'.

The third line of each test case contains 'N' space-separated integers representing the integer array 'cost'.

Output Format :

For each test case, print a single integer denoting the minimum index of the starting gas station if you are able to travel around the cycle once, otherwise print -1.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraint :

1 <= T <=50
1 <= N <= 10 ^ 4
0 <= GAS[i] <= 10 ^ 5
0 <= COST[i] <= 10 ^ 5

Where GAS[i] represents the ith element of 'GAS' array,
COST[i] represents the ith element of 'COST' array.

Time Limit: 1 sec

Accepted Answer

Brute Force

Run an iteration where ‘i’ ranges from 0 to N - 1, and for each ‘i’ check whether it is possible to complete the cycle from this index or not. This can be done as follow -:
- Initialize an integer variable ‘GASLEFT’ = 0, that will keep track of the amount of gas available at each station throughout the cycle.
- Run a loop where ‘j’ ranges from ‘i’ to ‘i + n’ and find the amount of gas left at each station ‘j mod n’. If the amount of gas left at some station is negative then we cannot complete the cycle. Otherwise ‘i’ will be our required answer.
- Return ‘i’ if it is possible to complete the cycle from the station ‘i’.
Return -1 if there is no station from where the cycle can be completed

Space Complexity: O(1)Explanation:

O(1).

We are not using any extra space here.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where 'N' is the number of gas stations.

Here, we have two nested iterations each run ‘N’ times in the worst case.

Accepted Answer

Greedy

You can notice that If the car starts at station ‘A’ and the first station it cannot reach is station ‘B’, it means any station between A and B can not reach B. We can use it to solve the problem in linear time.

Run an iteration where ‘i’ ranges from 0 to N - 1 and in each iteration do following.
- If the amount of gas available at station ‘i’ is less than the amount of gas required to move to the next station, then skip this station ‘i’ as it cannot be the starting index.
- Otherwise, initialize an integer variable ‘GASLEFT’ = 0, and run a loop to find out the first station from ‘i’ where ‘GASLEFT’ is negative. After that jump ‘i’ to the station where ‘GASLEFT’ first becomes negative.
- If you can run a complete cycle from ‘i’ without letting ‘GASLEFT’ negative then return this index ‘i’ as it will be our answer.
Return -1 if there is no station from where the cycle can be completed.

Space Complexity: O(1)Explanation:

O(1).

We are using constant space.

Time Complexity: O(n)Explanation:

O(N), where 'N' is the number of gas stations.

We are visiting every index of the array twice at max, hence making the complexity O(N).