gistfile1.java

import java.util.ArrayList;
import java.util.List;

/**
 * There is a one-way circular route from City A to City X. In between these 2 cities,
 * there are a number of cities separated by any distance. Each city has a petrol pump 
 * and holds a different storage capacity. The total petrol available in all the cities 
 * put together is say 'Z' litres. The total distance between City A to City X will be 
 * 'Z' kilo meters. Assume the bike has a mile-age of 1 litre per KM. 
 * Your goal is to around the circle, starting with no petrol. Find which city you will
 * start first, to ensure you wont run out of petrol mid-way.   
 * 
 * e.g. Cities:		A -> B -> C -> D -> E -> A
 * 		Distances:	  7    3    5    12   4
 * 		Capacity:	  5	   4    7     8   7
 * 
 * 		output: 	City E
 * 
 * @author raju rama krishna
 *
 */
public class PetrolPump {

	// Number of Cities
	int n = 0; 
	// Distance between cities, starting from A
	List<Integer> distances = new ArrayList<Integer>(); 
	// Petrol available at each city, starting from A
	List<Integer> capacities = new ArrayList<Integer>();		

	public static void main(String[] args) {
		PetrolPump pump = new PetrolPump();
		pump.setup();		
		pump.findCity();
	}
	
	public void findCity() {
		int max = 0;
		int city = 0;
		for( int i = 0; i < n; i++ ) {
			//This is the petrol saved or deficit for covering the journey
			//from city i to (i+1);
			int petrol = capacities.get(i) - distances.get(i);
			if(petrol > max) {
				max = petrol;
				city = i;
			}
		}
		//Transform index to City name
		char cityNm = (char)('A' +city);
		System.out.println("Start from city : " +cityNm);
	}
	
	private void setup() {
		n = 5;
		
		distances.add(7);
		distances.add(3);
		distances.add(5);
		distances.add(12);
		distances.add(4);
		
		capacities.add(5);
		capacities.add(4);
		capacities.add(7);
		capacities.add(8);
		capacities.add(7);
	}

}