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 

can you make it using queue

nice

A simple Java Solution

    int tour(int petrol[], int distance[])
    {
	int deficit=0, start=0,cal=0;
	for(int i=0;i<petrol.length;i++){
	    cal+=petrol[i]-distance[i];
	    if(cal<0){
	        start=i+1;
	        deficit+=cal;
	        cal=0;
	    }
	    
	}
	return (cal+deficit)>0 ? start :-1;
    }

@Seelam-Ramesh-Reddy

Failing for below test case

petrol - [5,1,2,3,4]
gas - [4,4,1,5,1]

@riteshsangwan

The solution I tried is GFG and it is working: https://practice.geeksforgeeks.org/problems/circular-tour/1#

@Seelam-Ramesh-Reddy

The return condition should have >= condition.

return (cal+deficit)>=0 ? start :-1;

This is because even if the extra petrol left is equal to the deficit petrol, the journey is possible.
This code also solves for the test case given by @riteshsangwan.

A simple Java Solution

    int tour(int petrol[], int distance[])
    {
	int deficit=0, start=0,cal=0;
	for(int i=0;i<petrol.length;i++){
	    cal+=petrol[i]-distance[i];
	    if(cal<0){
	        start=i+1;
	        deficit+=cal;
	        cal=0;
	    }
	    
	}
	return (cal+deficit)>0 ? start :-1;
    }

add >= in the return statement

Can anyone give the code in c or python?

C++ solution, passed in InterviewBit

int Solution::canCompleteCircuit(const vector<int> &petrol, const vector<int> &distance) {
    int deficit = 0, start = 0,cal = 0;
    if(petrol[0] == distance[0] && petrol.size() == distance.size())
        return 0;

	for(int i = 0; i < petrol.size(); i++){
	    cal += petrol[i] - distance[i];
	    if(cal <= 0){
	        start = i + 1; //path
	        deficit += cal; //remaining petrol
	        cal = 0;
	    }
	    
	}
	return (cal + deficit) >= 0 ? start : -1;
}

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)