Circular Tour Gas Station

In this class, We discuss Circular Tour Gas Station.

Readers can prepare a full competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Assume there is a circle.

There are N petrol stations in the circle.

You were given two arrays of size N.

1) One array shows the quantity of petrol in a gas station.

2) Another array shows the distance to the next gas station.

Note: One litre of petrol is enough to travel one unit distance.

Petrol quantity is given in litres.

Find the starting point from where a truck can start and complete a circle without exhausting the petrol.

Example:

Petrol: [4, 6, 7, 4]

Distance: [6, 5, 3, 5]

Output: 1

We need to start making a circle from the second gas station.

The index of a second gas station is 1.

We can not move to the second gas station when we start from the first gas station because the distance is 6.

The petrol. Available in the first gas station is 4.

Time complexity: O(N)

Space complexity: O(1)

Logic:

The step-by-step logic is explained in the video.

Code:

class Solution:

    def tour(self,lis, n):

        start = 0

        s = 0         

        d = 0       

        for i in range(n):

            s += lis[i][0] – lis[i][1]

            if s < 0:           

                start = i+1       

                d += s           

                s = 0           

        return start if (s+d)>=0 else -1

n=int(input(“enter n value”))

lis=[]

for i in range(n):

    k=[]

    x=int(input(“enter petrol value”))

    y=int(input(“enter distance value”))

    k.append(x)

    k.append(y)

    lis.append(k)

ob=Solution()

z=ob.tour(lis,n)

print(z)