# Circular tour

### Problem Statement
Suppose there is a circle. There are N petrol pumps on that circle. You will be given two sets of data.
1. The amount of petrol that every petrol pump has.
2. Distance from that petrol pump to the next petrol pump.

Find a starting point where the truck can start to get through the complete circle without exhausting its petrol in between.
Note : Assume for 1 litre petrol, the truck can go 1 unit of distance.

#### Test Case 1
**Input:**

    N = 4
    Petrol = [4, 6, 7, 4]
    Distance = [6, 5, 3, 5]
    Output: 1

**Explanation:** There are 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}. The first point from where truck can make a circular tour is 2nd petrol pump. Output in this case is 1 (index of 2nd petrol pump).

### Solution Approach
* Since the array distance kinds of takes distance[i] power from the truck while petrol array adds petrol[i] power to the truck, hence resultant power added to truck at particular station, i can be expressed as petrol[i]-distance[i];
* Therefor resultant power = [-2,1,4,-1], now we can think of it as a subarray sum problem and aim is to find the begining of the subarray that will suffise the give condition.
* if we start at index=1 then we can be able to complete the cycle.
* We will use kadane's algorithm to find the index.

#### Psuedo code
* find the power array, power[i] = petrol[i]-distance[i]
* now check if it's possible to complete the cycle, i.e sum of power's is non-negative.
* now take 2 varibles, current_sum and index.
* keep on adding power[i] to current_sum, if it becomes negative start over from next index.
* Now since you've already checked that it's possible to complete the cycle and got the index from kadane, so this index itself will be the answer.

## Code

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define fr(i,a,b)  for(ll i=a;i<b;i++)
#define rf(i,a,b)  for(ll i=a;i>=b;i--)
#define endl       "\n"
#define pri(x)     cout << x << "\n"
#define prin(x,y)  cout << x << " " << y << "\n"
#define pb         push_bacm
#define yes()      cout<<"YES"<<"\n"
#define no()       cout<<"NO"<<"\n"
#define errA(A)    for(auto i:A) cout<<i<<" ";cout<<"\n";
#define F          first
#define S          second
#define all(x)     x.begin(), x.end()
ll mod = 1e9+7;
ll N=2e6;
using namespace std;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x)
	{
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const 
	{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void outwer(){
    ll n=0;
    cin>>n;
    vector<ll>petrol(n);
    vector<ll>dist(n);
    fr(i,0,n){
        cin>>petrol[i];
    }
    fr(i,0,n){
        cin>>dist[i];
    }
    // power array , can tweak the input but for now let's make another array
    ll total =0;
    vector<ll>power(n);
    fr(i,0,n){
        power[i] = petrol[i]-dist[i];
        total +=power[i];
    }
    // check if it is possible to reach any how
    if(total<0){
        cout<<"Not reachable"<<endl;
        return;
    }
    ll sum=0,ans=0;
    fr(i,0,n){
        sum +=power[i];
        if(sum<0){
            sum=0;
            ans=i+1;
        }
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    ll t=0;
    cin>>t;
    while(t--){
        outwer();
    }
}

Time Comeplexity: O(N)
Space Complexity: O(N)

can be done in constatant space if input as mutable.