Petrol Pump Problem

Problem Statement:

       Budh International Circuit organised Formula 1 Racing in Noida.

While inspecting the circuit the management found that the fuel tanks that were setup had limited capacity of fuel and it also happened that if a car starts from some fuel tank it wont be able to reach the other fuel tank.

Now the management had the challenge of fixing point of start of race such the race completes at the same point.

Given Inputs:

1. Fuel capacity at each fuel pump.
2. Distance to the next fuel pump.
3. There exist a point from where if the race is started it would complete.

To Find: 
      Find out the petrol pump starting at which you can go around and come back to that particular petrol pump.

Solution :


Refer to full Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

/** * Get the Starting Point of the Circular Trip * @return index of the petrol pump if solution exist , * else -1 if solution doesnt exist */ public static int getStartIndex(int[] dist , int[] petrol){ int nPumps= petrol.length; int start , currentPetrol; int i=start=0; while(start < nPumps) { currentPetrol= petrol[i] - dist[i] ; while(currentPetrol >= 0) { i= (i+1) % nPumps ; currentPetrol += petrol [i] - dist[i] ; if(i==start) return start; } start = ++i ; i= i % nPumps ; } return -1; }

Please comment if you liked this post, also any comments or suggestion are most welcome.

Happy Coding !! :)