You are viewing a single comment's thread. Return to all comments →
I'm also confused why this is under the queue section. I solved it without a queue, stack, list, etc. Just keep track of how much fuel is in the tank. Once it goes below zero then reset the fuel in the tank to zero and set the pump to the next pump.
using namespace std;
unsigned int n;
cin >> n;
long long tank = 0;
unsigned int pump = 0;
for (unsigned int i = 0; i < n; ++i)
unsigned int liters;
unsigned int kilometers;
cin >> liters >> kilometers;
tank += (long long) (unsigned long long) liters -
(long long) (unsigned long long) kilometers;
if (tank < 0)
pump = i + 1;
tank = 0;
cout << pump << endl;
According to your algorithm if we supply the following output
it gives the output as 2 wheras technically there is no solution to this scenario as you are only considering from the point until the end of the list whereas it should be considered as a queue which wraps around. Please correct me if I am wrong.
It was a while ago so I can't say for sure what my assumptions were. If I had to guess I would say I was under the assumption a solution must exist for the data supplied and thus my algorithm works correctly under that assumption. At least I think it does. Do you have an example where it doesn't?
Since no where it is asked to return -1 if solution does not exists, your assumption is correct. A solution must exists. Hence, we do not need to use a circular queue. :)
The problem does not require Queue structre to use but the logic/understanding of the queue helps in breaking down the solution.
You are right :)
According to u passing input
answer would be 1,but technically answer should be not possible
you will get a wrong output for this case the ans to this input should be 0(1st petrol pump) but your code will give 1(2nd petrol pump).