# Gas Tank

Posted: 9 Sep, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
``````
Approach 1
• 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