Circular Tour

// C++ program to find circular tour for a truck 
#include <bits/stdc++.h> 
using namespace std; 

// A petrol pump has petrol and distance to next petrol pump 
class petrolPump 
{ 
	public: 
	int petrol; 
	int distance; 
}; 

// The function returns starting point if there is a possible solution, 
// otherwise returns -1 
int printTour(petrolPump arr[], int n) 
{ 
	// Consider first petrol pump as a starting point 
	int start = 0; 
	int end = 1; 

	int curr_petrol = arr[start].petrol - arr[start].distance; 

	/* Run a loop while all petrol pumps are not visited. 
	And we have reached first petrol pump again with 0 or more petrol */
	while (end != start || curr_petrol < 0) 
	{ 
		// If curremt amount of petrol in truck becomes less than 0, then 
		// remove the starting petrol pump from tour 
		while (curr_petrol < 0 && start != end) 
		{ 
			// Remove starting petrol pump. Change start 
			curr_petrol -= arr[start].petrol - arr[start].distance; 
			start = (start + 1) % n; 

			// If 0 is being considered as start again, then there is no 
			// possible solution 
			if (start == 0) 
			return -1; 
		} 

		// Add a petrol pump to current tour 
		curr_petrol += arr[end].petrol - arr[end].distance; 

		end = (end + 1) % n; 
	} 

	// Return starting point 
	return start; 
} 

// Driver code 
int main() 
{ 
	petrolPump arr[] = {{6, 4}, {3, 6}, {7, 3}}; 

	int n = sizeof(arr)/sizeof(arr[0]); 
	int start = printTour(arr, n); 

	(start == -1)? cout<<"No solution": cout<<"Start = "<<start; 

	return 0; 
} 


// This code is contributed by rathbhupendra 

int tour(petrolPump p[],int n)
{
    int front=0,rear=0;
    int bal=0,prevbal=0;
    while(rear!=n)
    {
        if(front==rear)
        {   
            prevbal+=bal;
            bal=0;
        }
        bal+=(p[rear].petrol-p[rear].distance);
        rear++;
        if(bal<0)
        front=rear;
    }
    if(bal+prevbal>=0)
    return front;
    else
    return -1;
}

int Solution::canCompleteCircuit(const vector &a, const vector &b)
{
int sum_a = 0;
int sum_b = 0;
for(int i=0;i<a.size();i++)
{
sum_a+=a[i];
sum_b+=b[i];
}

if(sum_b>sum_a)
    return -1;


int n = a.size();
int f = 0;
int r = 0;
int bal = 0;
int cnt = 0;
while(cnt<n)
{
    bal += a[r]-b[r];
    if(bal<0)
    {
        r++;
        f=r;
        bal=0;
        cnt=0;
        continue;
    }
    if(cnt==n-1)
        return f;
    cnt++;
    r = (r+1)%n;
}

}

C++ Easy

can you make it using queue

yes with deque

int tour(petrolPump p[],int n)
{
//Your code here
int totalGas = 0;
int totalCost = 0;

    for(int i=0; i<n; i++){
        totalGas += p[i].petrol;
        totalCost += p[i].distance;
    }
    
    if(totalCost > totalGas){
        return -1;
    }
    
    int ans = 0;
    int remaining_gas = 0;
    
    for(int i=0; i<n; i++){
        
        remaining_gas += p[i].petrol-p[i].distance;
        
        if(remaining_gas < 0){
            ans = i+1;
            remaining_gas = 0;
        }
    }
    return ans;
}

class petrolPump:
def init(self, petrol, distance):
self.petrol = petrol
self.distance = distance

def printTour(arr, n):
# Consider first petrol pump as a starting point
start = 0
end = 1

curr_petrol = arr[start].petrol - arr[start].distance

while end != start or curr_petrol < 0:
  
    while curr_petrol < 0 and start != end:
        curr_petrol -= arr[start].petrol - arr[start].distance
        start = (start + 1) % n
        if start == 0:
            return -1

    curr_petrol += arr[end].petrol - arr[end].distance
    end = (end + 1) % n

return start

Driver code

if name == 'main':
arr = [petrolPump(6, 4), petrolPump(3, 6), petrolPump(7, 3)]

n = len(arr)
start = printTour(arr, n)

if start == -1:
    print("No solution")
else:
    print("Start =", start)