### Find the first circular tour that visits all petrol pumps

##### Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

- The amount of petrol that every petrol pump has.
- Distance from that petrol pump to the next petrol pump.

For example,

Let there be 4 petrol pumps with amount of petrol and distance to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}.

**Solution:**

- We’ll pick any petrol pumps as starting point,
- Now there could be two possible than
- Either, we have enough petrol to reach next petrol pumps, in that case
- We’ll move to next petrol pump

- Or, we haven’t enough petrol to reach next petrol pumps, in that case
- We’ll back to one step back from starting point.

##### Algorithm:

- Start from 0th petrol pump
- Set
`startIndex = 0, endIndex = startIndex + 1, availablePetrol = P0.petrol and distance = P0.distance`

- Set
- Iterate till
`startIndex != endIndex`

- Iterate till
`startIndex != endIndex and availablePetrol < distance`

- Move one step back from starting point i.e.
`startIndex = (startIndex - 1 ) % totalPetrolPump`

- Update availablePetrol i.e.
`availablePetrol += P[startIndex].petrol`

- Update distance i.e.
`distance += P[startIndex].distance`

- Move one step back from starting point i.e.
- Move one step next i.e.
`endIndex = (endIndex + 1) % totalPetrolPump`

- Update availablePetrol i.e.
`availablePetrol += P[startIndex].petrol`

- Update distance i.e.
`distance += P[startIndex].distance`

- Iterate till
- If our availablePetrol is less than distance then,
- throw “Not possible” exception

`Return startIndex`

Latest Source Code:

Github: PetrolPumpsCircularTour.java

**Output:**

Starting Point : C