Truck Tour HackerRank Problem
Task:- Given the amount of petrol in each petrol pump and the distance to the next petrol pump. Find the minimum index of the petrol pump we can start and then visit every petrol pump.
The petrol pumps are placed in circular format so we can visit index 0 after index (N-1).
Brute Force Approach:- We can start from each index and check whether we are able to complete the loop. If not we start again from the next index. We keep on doing this till we get the first index from which we start and are able to complete the whole loop.
The time complexity of this approach will be O(N²) as for each index we traverse at the most N elements.
Brute Force Code:-
Efficient Approach:- To complete the loop, we have to make sure that the petrol in the truck does not become negative at any point/index. We can calculate the surplus distance for each petrol pump i.e- the extra distance we can cover after reaching the next petrol pump. We can easily get this by subtracting the distance to next petrol pump from the petrol in current petrol pump ( petrol[i]-distance[i] )
Note that this is possible because we can cover unit distance in one unit of petrol.
Now we have the extra distance for each petrol pump and we have to see whether we can complete the loop from a particular pump. So we start from the first pump and maintain a variable “xsum” which denotes how much petrol we have left and we keep adding the surplus of each pump in the “xsum” variable. If at any point this variable becomes negative it means we cannot complete the loop with the current starting point and we reset this variable and start from the next petrol pump.
Note:- We do not start again from the next pump where we started from in the previous iteration but we start again from the pump where the “xsum” variable goes negative. This is because if we reached a petrol pump and added it’s surplus and still cannot complete the loop we would not be able to complete the loop even if we start from some other point till that pump.
Consider an example :
Petrol = [ 3 , 4 , 6 , 3 , 4 , 3 , 7 ]
Distance = [ 2 , 4 , 9 , 1 , 3 , 6 , 2 ]
Surplus = [ 1 , 0 , -3 , 2 , -1 , -3 , 5 ]
Execution :-
Initially xsum=0 and we start from i = 0 (first pump)
Add the surplus to the xsum, xsum = 1
- Now i = 1 , xsum = 1+0 = 1
- i = 2 , xsum = 1–3 = -2
Xsum becomes negative that means we cannot start from i=0 to complete the loop
Note that we can neither start from i=1 or i=2 to complete the loop
So we start from i = 3 and reset the xsum. xsum = 0
- i = 3 , xsum = 0 + 2 = 2
- i = 4 , xsum = 2–1 = 1
- i = 5 , xsum = 1–3 = -2
xsum becomes negative that means we cannot start from i=3 to complete the loop
Note that we can neither start from i = 4 or i = 5 to complete the loop
So we start from i = 3 and reset the xsum. xsum = 0
- i = 6 , xsum = 0 + 5 = 5
Then we go to first pump again
- i = 0 , xsum = 5 + 1 = 6
- i = 1 , xsum = 6 + 0 = 6
- i = 2 , xsum = 6–3 = 3 and so on till i=5 we complete the loop
So the answer is 6
Note:- We do not need to go to the first pump after we reach the last pump because it is given that a solution always exists so if we reach the last petrol pump we will definitely complete the loop
Efficient Code:-
