CareerCup

First find the differences C1-D1, C2-D2,C3-D3…..CN-DN. Differences represent the excess gas or gas shortage of gas to reach the next station. Ideally we should start from a station which will give us maximum cumulative excess gas.
If we apply variant of Kadane Algorithm(maximum subsequence algorithm) for circular List. Then we will get the starting point.
We need to take care of one more corner case that sum of all (cx-dx) is negative then there is no solution possible.

Checking each station in the circle from the head if the gas it provide can afford the distance to the next station. The gas count getting by gas minus distance I call it as gasAdded. The value can be positive or negative.
Starting from the first station and check the gasAdded in each station seeing if it is positive, if so, it can be considered as the start station. A counter will be set as the sum of gasAdded values. Going down the circle and add the gasAdded value of each station to the counter. Whenever the counter changed negative, the start station will be changed to the station next to the current checking one.
The stations between two start station can be considered as a big virtual station that can only provide negative gas than the distance. Since the total gas can cover all the distance, the gas in the left stations should larger than the left distance. Before the end of the checking, the matching station will be found.
//The CircuitLinkedList is implemented myself.
#include "CircuitLinkedList.h"
#include <iostream>
#include "malloc.h"
using namespace std;
struct Station
{
int gas;
int distance;
};
int main()
{
CircuitLinkedList<Station* > list;
Station ss[10]={{8,7},{9,6},{8,10},{5,7},{9,9},{8,2},{1,7},{6,4},{7,6},{9,10}};
for(int i = 0; i < 10; i++)
{
Station* s = (Station*)malloc(sizeof(Station));
s->distance = ss[i].distance;
s->gas = ss[i].gas;
list.inseartNode(new Node<Station*>(s));
}
Node<Station*>* current = list.head;
Node<Station*>* startPosition = list.head;
int currentGas = 0;
while(current != list.last)
{
if((currentGas+(current->data->gas - current->data->distance))< 0)
{
currentGas=0;
startPosition = current->next;
}
else
{
currentGas+= (current->data->gas - current->data->distance);
}
current= current->next;
}
cout<<"The start station is "<<startPosition->data->gas<<" , "<<startPosition->data->distance<<endl;
return 0;
}

Solution

choose the first station as the starting point

maintain the total capacity and total distance from the starting station to the current station,

if total capacity is less than the total distance, no gas station between the starting station and the current one can be the starting station, choose the next station as starting point, add the total capacity and distance to the total capacity and distance and from 0 to start (avoiding recalculation)
when the pointer reach the last element, verify if the total capacity is less than total distance

ideone.com/Xx4S2c

public int getStartingStation(int[] cost, int[] dist)
        {
                int start = 0;
                int capacityFromStart = 0; // total capacity from the starting station
                int distFromStart = 0; // total distance from the starting stations
                int capacityToStart = 0; // total capacity from 0 to the starting station (exclusively)
                int distToStart = 0; // total distance from 0 to the starting station (exclusively)
                for(int i = 0; i < cost.length; i++) {
                        capacityFromStart += cost[i]; 
                        distFromStart += dist[i];
                        if(capacityFromStart < distFromStart) {
                                capacityToStart += capacityFromStart;
                                distToStart += distFromStart;
                                start = i + 1;
                                capacityFromStart = 0;
                                distFromStart = 0;
                        }
                }
                if(capacityFromStart + capacityToStart < distFromStart + distToStart) throw new NoSuchElementException();
                return start;
        }

For the given problem, we have start from the station N and proceed towards n-1,n-2 till 1.
The distance from n to n-1 is always n.
station 5 : Fill 5 litres and travel 5 km towards station 4
station 4: Gas will be over and fill 4 litres and travel 4km towards station 3 .

Likewise repeat till you reach 1.

The stations can consist of a directed graph. Using the Ci-Di as the weight, the shortest path algorithm, like Bellman-Ford or SPFA algorithm, can be used to calculate a optimal path.

It is just a idea...

Build Ci-Di array and find the element from which we should start summing of all the array items so that the current sum is always greater than 0:

var stationsCapacity = [1,4,4,7];
var distances = [2,3,5,6];

var remainingGas = [];

for(var i=0; i<stationsCapacity.length;i++)
  remainingGas.push(stationsCapacity[i] - distances[i]);


var startStation;
for(var i=0; i<remainingGas.length;i++){
  var sum = remainingGas[i];
  if(sum < 0)
    continue;
  var fits = true;
  for(var j=i+1;j<remainingGas.length;j++){
    sum+=remainingGas[j];
    if(sum < 0){
      fits = false;
      break;
    }
  }
  if(sum>0){
    for(j=0;j<i;j++){
      sum+=remainingGas[j];
      if(sum < 0){
        fits = false;   
        break;
      }
    }
  }
  if(fits){
    startStation = i;
    break;
  }
}

console.log(startStation);

First of all if we draw the figure:
----for the starting station: we will see that for each station on the circle there are two possible ways clockwise or counter-clockwise. So lets say we are at station one, we get here gas for C1 distance, so now we can either go to station 2 or station n. (If C1 < D1 then we can only choose Sn, and if C1 < Dn then we can only choose S1, otherwise you can try either of them).

---- I think that analyzing this, the best solution is to do something like this :

foreach currentStation = 1..n{
   clockDirection = -D[ getNextStation (currentStation) ] + C[ currentStation ];
   counterClockDirection = C[ currentStation ] - D[ getLastStation (currentStation) ];
   int gas = -1;
   if(clockDirection > 0){
      gas = goToNextStation(currentStation, getNextStation(currentStation), true, clockDirection);
  }
  if(counterClockDirection > 0){
     gas = Math.max(gas, goToNextStation(currentStation, getLastStation(currentStation), false,counterClockDirection);
  }

  if(gas>=0) return currentStation;
}
return -1; // there is no valid station to start from
-----------------------------------------------------------------------------------
int getLastStation(in station){
  if(station==1) return n;
   return station-1;
}

-----------------------------------------------------------------------------------

int getNextStation(int station){
   if(station==n) return 1;
   return station+1;
}

-----------------------------------------------------------------------------------

int goToNextStation(Station startedFrom, Station stationToGo, boolean clockWise, int availableGas){...}

- so if we arrive at startedFrom then return availableGas
- if not , then check which way we are going and add the clockWiseDirection or the counterClockDirection value to the available gas, and call goToNextStation(startedFrom, getNext /getLast Station(stationToGo), clockWise, theNewAvailableGas).

What I am trying to say is that we should make like a preview for each station to see if it will fit as a starting station. We cannot choose a station to be the starting one unless we know for sure that if we run the alg starting from it , we will get a valid result. So we don't know that unless we check it first.

In a circle there are N number of Gas filling stations which can provide you will gas of capacity C1, C2…CN. Distance between filling station is D1, D2, D3……DN. Considering your vehicle will consume 1 volume of gas per distance. Find the filling station from which you should start the journey so that you will never get short of Gas.

Just a change, What is the minimum number of stations where we need to fill the gas such a way that we never get short of the gas ?

Let's construct a matrix as follows:

C(i,(i+1) % n) = Ci - Di for all 0 <= i <= n - 1 (zero based index)
C(i, (i+k) % n) = Sum (C(j, j+1 % n)) for all i <= j < k & for all 2 <= k <= n

Solution is to that find 'i' such that c(i,i) is maximum.

Complexity: O(n^2). Space O(n^2) for remembering the previously computed values.

GasLeft[j] = GasLeft[i] + gas[i] - distance[i] (start point <= i < j)
GasLeft array keeps the record that the max gas can be left when arrive gas station j (starting from a certain gas station). If we find at some gas station the gas left is less than zero, it means the car can never reach that gas station.
Now we apply this idea to every gas station on the circle, and return the first gas station that has all its GasLeft positive.

Check, if round trip is possible when starting from 0th station. If gas is always >=0 on arrival at every station until the starting station comes back. Then, answer is 0th station.

If gas is <0 at any station, then, check it again by starting at 1st station.

Repeat checking until round trip is possible until you checked for nth station. Where ever it is possible answer is that station number.

If gas is not always >=0 on arrival until you finish checking for starting station as nth one, then, answer is "Stating at no station can complete the round trip"

int getStartStation(int[]c, int [] d){
		int startStationNo=-1;
		int n=c.length;
		int gasAvailable=0;
		for(int i=0;i<n;i++){	
			gasAvailable=0;
			System.out.println("If Starting Station is : " + (i));
			for(int j=i; j<n;j++){		
				System.out.println("  Available gas before filling at : "+(j)+" = " + gasAvailable);
				//if(i<n-2){
					gasAvailable += c[j]-d[j];
				//}else gasAvailable += c[j]-d[0];
				System.out.println("  Gas added="+c[j]+". To travel = "+d[j]+" Available gas on arrival at stn "+(j+1)+" = " + gasAvailable);
				if(gasAvailable<0){
					//gasAvailable=0;
					break;
					
				}
			}
			if(i>0 && gasAvailable>=0){
				for(int k=0;k<i;k++){
					System.out.println("  Available gas before filling at : "+(k)+" = " + gasAvailable);
					
					gasAvailable += c[k]-d[k];
					System.out.println("  Gas added="+c[k]+". To travel = "+d[k]+". Available gas on arrival at stn "+(k+1)+" = " + gasAvailable);
					if(gasAvailable<0){
						//gasAvailable=0;
						break;
					}
				}
		    }
			if(gasAvailable>=0){
				startStationNo=i;
				break;
			}		
		}
		if(startStationNo>=0){			 
			System.out.println("Station to start for completing round trip ="+(startStationNo));
		}else System.out.println("Stating at no station can complete the roundtrip");
		return  startStationNo;
	}

Time complexity O(N*2).
Maintain the difference of Ci-Di for each station in an array. Then for each element in the array traverse the remaining array in a circular fashion so that at no point the residual fuel is negative. Below code gives an idea and prints all the valid points. Can be modified to return the first node also.

void func(int ci[],int di[],int n)
{
     int diff[n],i,j,s,flag;
     for(i=0i<ni++)
     temp[i]=ci[i]-di[i];
     flag=0;
     for(i=0;i<n;i++)
     {
                     if(diff[i]>=0)
                     {
                                   s=arr[i];
                                   j=(i+1)%n;
                                   while(j!=i)
                                   {
                                              s+=arr[j];
                                              if(s<=0)
                                              break;
                                   }
                                   if(j==i)
                                   {
                                           flag++;
                                           printf("\n valid position :%d",i);
                                   }
                     }
     }
     if(!flag)
     printf("no valid position found");
     return;
}

This problem is Maximum sum for subarray in an array of +ve and -ve numbers for a circular array. Make the circular array with the difference Ci and Di. The starting chunk of the subarray guarantees that we will not fall short of Gas. We should make sure we should evaluate this for either direction . Complexity is O(n) + O(n) = O(n)