I have a doubt with the question

#1

In the given testcase, when we reach at the last checkpoint why do we have to buy petrol from it? We have already reached our destination right? and ans should be 5

#2

It also has to cross (n-1)th checkpoint to reach the destination,
I know Also checkpoint N−1 will lead to his final destination. , is ambiguous, but it means, after crossing (n-1)th checkpoint, you will reach destination.

#3

Here is my code which got n^2 time complexity thus i m getting tle https://ide.codingblocks.com/s/324216

#4

Hey @sshreya2912
Here is O(n) approach:
This is a simple greedy problem. We just need to buy petrol from the minimum possible rates checkpoints. Lets say we are at checkpoint X. Now there are X+1 checkpoints up to this checkpoint. We can easily see that for buying petrol for going to checkpoint X+1 , we just need to find the minimum possible C[i] where i can be from 1 to X+1 . Thus, we can just compare the minimum petrol rate till now(lets say denote it by (mi) at each of the checkpoint with the checkpoint rate i.e. C[i] . Now two possible cases arise:

  • First Case: mi <= C[i], No need to update mi i.e. petrol for this checkpoint has to be bought with the rate .
  • Second Case: mi > C[i] , We need to update mi and petrol for this checkpoint has to be bought with the new rate i.e. C[i] .

After iterating through all checkpoints following the above algorithm will lead to minimum travel cost.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.