Gas Tank

Posted: 9 Sep, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
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
Try Problem