There are N gas stations along a circular route, where the amount of gas at station i is arr[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). At the beginning of the journey, the tank is empty at one of the gas stations. Write a program to return the minimum starting gas station’s index so that you can travel around the circuit once, otherwise return -1

Problem Note

  • Completing the circuit means starting at i and ending up at i again.
  • If there exists a solution, it is guaranteed to be unique.
  • Both input arrays are non-empty and have the same length.
  • Each element in the input arrays is a non-negative integer.

Example 1

Input: 
arr[] = [11,12,13,14,15]
cost[] = [6,8,10,2,4]
Output: 3

Explanation:
Begin at station 3 (index 3) and fill up with 14 unit of gas. Gas available in Tank = 0 + 14 = 14
Travel to station 4. Gas available in tank = 14 - 2 + 15 = 27
Travel to station 0. Gas available in tank = 27 - 2 + 1 = 27
Travel to station 1. Gas available in tank = 27 - 6 + 2 = 23
Travel to station 2. Gas available in tank = 23 - 8 + 3 = 18
Travel to station 3. The cost is 10.Your gas is enough to travel back to station 3.Therefore, return 3 as the starting index.

Example 2

Input: 
arr[] = [2,3,4]
cost[] = [3,4,3]
Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Gas available in tank = 0 + 4 = 4
Travel to station 0. Gas available in tank = 4 - 3 + 2 = 3
Travel to station 1. Gas available in tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.Therefore, you can't travel around the circuit once no matter where you start.