I'm trying to solve the following HackerRank problem (similar problem also can be found here).

Truck Tour

Suppose there is a circle. There are petrol pumps on that circle. Petrol pumps are numbered from 0 to N (both inclusive).

You have two pieces of information corresponding to each of the petrol pump:

• the amount of petrol that particular petrol pump will give,
• the distance from that petrol pump to the next petrol pump.

Initially, you have a tank of infinite capacity carrying no petrol. You can start the tour at any of the petrol pumps.

Calculate the first point from where the truck will be able to complete the circle. Consider that the truck will stop at each of the petrol pumps. The truck will move one kilometer for each litre of the petrol.

The input of the method is a matrix Nx2 represented as a nested list List<List<Integer>>, where N is the number of petrol pumps (size of the list).

Each of the pumps (inner list List<Integer>) has 2 elements that correspond to the amount of petrol the pump gives and the amount of petrol required to reach the next pump (see detailed description in the links above).

We need to find the index of the first pump that would allow to visit all N petrol pumps in a circular fashion.

My code seems to be fine, but Hackerrank says that it fails in some situations. What am I missing here?

public static int truckTour(List<List<Integer>> petrolpumps) {
    
    long tank;
    
    for(int i = 0; i < petrolpumps.size(); i  ){
        if(petrolpumps.get(i).get(0) >= petrolpumps.get(i).get(1)){
           
            tank = (petrolpumps.get(i).get(0) - petrolpumps.get(i).get(1));
            
            boolean good = true;
            
            for(int j = 0; j < petrolpumps.size(); j  ){
                int index = j   i;
                
                if(index > (petrolpumps.size() - 1))
                    index = index % petrolpumps.size();
                
                tank  = (petrolpumps.get(index).get(0) - petrolpumps.get(index).get(1));
                
                if(tank < 0){
                    good = false;
                    break;
                }
            }
            
            if(good)
                return i;
        }
    }
         
    System.out.println("=/");
    return -1; 

}

CodePudding user response：

Your mistake is rooted in the initialization of the tank variable. You double-count the amount of petrol provided by the pump i - it gets added to the tank first while initializing the tank and second time in the inner for-loop when j=0. For that reason, you're getting incorrect results.

To fix it, instead of this line:

tank = (petrolpumps.get(i).get(0) - petrolpumps.get(i).get(1));

Simply initialize the tank to zero. And you can also remove the declaration tank before the outer for-loop, to confine this variable to a more narrow scope (which is a good practice).

long tank = 0;

This fix is sufficient to pass all the test cases on HackerRank.

There are also a few changes can be done to make the solution more readable and a bit more concise.

I would rather use if (conditionIsNotMet) continue; then if (conditionIsMet) { doStuff } to reduce the level of nesting.

And since we can't use the index of the inner for-loop as is, but instead have to perform some extra actions with it (check if the size exceeded, then apply modulo %) I would prefer using while loop.

That's how it can be done (this solution is tested as well):

public static int truckTour(List<List<Integer>> petrolpumps) {
    
    final int size = petrolpumps.size();
    
    for (int start = 0; start < size; start  ) {
        if (petrolpumps.get(start).get(0) < petrolpumps.get(start).get(1)) continue;
        
        long tank = 0;
        int position = start;
        int pumpCount = 0;
        
        while (true) {
            if (pumpCount == size) return start; // all pumps has been visited
            if (tank < 0) break;                 // not enough petrol to move further

            tank  = petrolpumps.get(position % size).get(0) - petrolpumps.get(position % size).get(1);
            
            position  ;
            pumpCount  ;
        }
    }
    return -1;
}