Please help me with the logic of this question

#1

please help me understand how to approach this question

#2

Hey @be10046.19
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.