We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

This goes into an infinite loop. What happens is-for a series of 0 to 6 here, it exhausts first at the node 4, starts off again at 4, and then after exhauting at node 6, arrives at 0 again, and the cycle repeats. We can use a hashmap mayB to mark off the ones used as start node. Just thinking out aloud.

The problem did not specify what to ouput for an invald input, but we can output -1 or something.

All test cases have a solution, i.e., there is no case where there's no solution. We have to make sure that our test case has a solution. The mentioned test case clearly has no solution.

Yeah it is because you are never going to reach the starting point no matter from where you start from. If you check properly you total fuel is more than the total distance to be covered where mileage is 1km per litre

That should be "total fuel is LESS than the distance to be covered" so there's no solution. The problem guarantees a solution for given data so this data (total fuel = 19, total distance = 25) does not qualify. There is always a solution if (total fuel >= total distance) but no solution if (total fuel < total distance).

Thanks for this. This is an elegant idea. Because of this I can agree that this problem can be used to practice queue data structure. Following this idea I have implemented following,

publicclassTruckTour{publicQueue<int>PPQueue;publicvoidTakeInput(){PPQueue=newQueue<int>();intn=int.Parse(Console.ReadLine());while(n-->0){string[]tokens=Console.ReadLine().Split();PPQueue.Enqueue(int.Parse(tokens[0])-int.Parse(tokens[1]));}}// get 0 based index of starting Petrol PumppublicintGetStartingPumpIndex(){// start with an initial queue// start index is 0// keep popping items// whenever it fails forward it to the next tage..intpass_count=0;ints_fa=0;intpp_start_index=0;while(pass_count<PPQueue.Count){intr_fa=PPQueue.Dequeue();// residue of fuel amounts_fa+=r_fa;if(s_fa<0){s_fa=0;pp_start_index+=pass_count+1;pass_count=0;}elsepass_count++;PPQueue.Enqueue(r_fa);}returnpp_start_index;}}

## Truck Tour

You are viewing a single comment's thread. Return to all comments →

Queue-based solutuon, just in case...

Thanks a lot man!

Great solution, kind of disappointed I didn't figure it out like this.

Thanks man. It passed all the given test cases. But this one(not given in hackerrank) failed:

7

5 2

1 2

3 3

2 5

6 2

1 5

1 6

Or m I missing something?

Sorry, I have no access to my laptop to check it. What is result of my code on this input, and what is the answer/sequence you expect for fhis input?

This goes into an infinite loop. What happens is-for a series of 0 to 6 here, it exhausts first at the node 4, starts off again at 4, and then after exhauting at node 6, arrives at 0 again, and the cycle repeats. We can use a hashmap mayB to mark off the ones used as start node. Just thinking out aloud.

The problem did not specify what to ouput for an invald input, but we can output -1 or something.

I believe there is always a solution.

All test cases have a solution, i.e., there is no case where there's no solution. We have to make sure that our test case has a solution. The mentioned test case clearly has no solution.

Yeah it is because you are never going to reach the starting point no matter from where you start from. If you check properly you total fuel is more than the total distance to be covered where mileage is 1km per litre

That should be "total fuel is LESS than the distance to be covered" so there's no solution. The problem guarantees a solution for given data so this data (total fuel = 19, total distance = 25) does not qualify. There is always a solution if (total fuel >= total distance) but no solution if (total fuel < total distance).

Total Sum At All Petrol Pumps Petrol = 19 Ditance = 25 > 19

So it will go into infinite loop. Because Total Distance Itself is not withing the total capacity Of all the petrol pumps.

It was a simple check mam...!!

efficient and clean solution!

how do u come up with such great solutions?

It's O(n^2) in worst case.

Thanks for this. This is an elegant idea. Because of this I can agree that this problem can be used to practice queue data structure. Following this idea I have implemented following,

full source-code link

For better understanding it's good to look at 2 goals specified by the problem description,

Maybe I'm missing something, but why do you increment start by passed+1?

Are you referring to this line?

brilliant use of enqueue