- Practice
- Data Structures
- Queues
- Truck Tour
- Discussions

# Truck Tour

# Truck Tour

Gladdyu + 9 comments This was the absolute easiest problem 'Difficult' problem on this site so far. Possible in linear time and you don't need any queues whatsoever.

**Spoiler alert:**Integration and global minima.morcanie + 1 comment agreed

gaurav_321 + 1 comment agreed

mr_sanat + 0 comments agreed

kiner_shah + 1 comment How does integration involve over here? Can u plz explain? I m nt getting it!

FlintLockwood + 1 comment I dont it too pls explain.

Gladdyu + 5 comments Consider the amount of fuel you have in your tank as a function of the amount of stations you have passed (the integral of the change in fuel {gained - used} per station results in the amount of fuel for every station, the fundamental theorem of calculus). Now: this function has to be positive for every station because you cannot ever have negative fuel in your tank. This only happens whenever you start at a global minimum of this function. You are essentially shifting the function vertically, setting it to zero at your starting point and if this is the lowest point then all other points will be positive.

This is assuming that a full circle will not result in a net fuel loss (then you cannot complete the circle) and furthermore that there are no more than 1 global minima (then you get stuck with exactly 0 fuel at the position of the second global minimum).kaushal087 + 1 comment Your solution's complexity is O(N^2) as you will start from

0th to Nth

1st to 0th

2nd to 1st

3rd to 2nd

...

Nth to N-1th

each step will take N time and there are N step. So the worst case time complexity will be O(N^2). Correct me if I am wrong. I have done this way and I have used loop inside loop and it's time complexity is O(N^2).morcanie + 2 comments I don't think that's the method Gladdyu is proposing. His method would have worst case complexity of O(N), because all you do is go through the loop once, and at each stop record the total amount of gas up to that point, which could be negative if there is a greater amount of distance traveled to that point than gas gained. Then the point with the minimum amount of gas is the answer.

Gladdyu, I think there's one error in what you said though; if there are two global minima, it doesn't matter, because that would just mean that you'd get to the second minima with 0 gas, but gain however much gas is there, so you can keep going.

Gladdyu + 0 comments Yep, you're correct!

drew_verlee + 1 comment Is there a comment from Gladdyu im missing? He isnt purposing an algorithm anywhere I can see (a required element for their to be an upper bound).

Gladdyu + 1 comment It appears as if some of my comments got deleted by someone...

drew_verlee + 0 comments without any investigation my guess is a mod, persumable because you linked a solution of some sort. They should do a [comment deleted because xyz] not just ninja remove them. Again this speculation.

Thanks for the update.

chetangautam + 0 comments I didnt understand your solution. Can you please explain again? I solved it with O(N^2). Thanks.

mehtabhavesh9 + 0 comments Clarification - You start one station after the station you see the global minimum so you never hit the global minimum.

piyushmishra + 0 comments Nice explanation !!!

piyushmishra + 1 comment I have read that it is impossible to find a global minimum for any arbitary function.Could it be a case here? http://mathworld.wolfram.com/GlobalMinimum.html

regatti_1 + 0 comments Here the values of the function at all possible indices (this is the key) are given.So all you need to do is to find the minimum by traversing once.

btamada + 1 comment I think the point of the challenge is to solve the problem using a Queue, rather than just trying to solve it using any possible solution.

pflau + 1 comment But when I used a queue it timed out. I did without a queue and it passed all tests.

shashisuman + 0 comments LMAO

PRASHANTB1984 + 0 comments Thanks for the feedback. However, the level of difficulty sometimes varies as perceived by differnet users, to some extent!

driftwood + 0 comments Can't be that easy as you failed to solve it using queue, as the problem and category intended!

https://www.hackerrank.com/challenges/truck-tour/forum/comments/128778

pflau + 0 comments I totally agree. But it still got me because it was under the Queues topic and I thought I needed to use a queue. But I ended up not needing to use any advanced container AT ALL.

codeharrier + 0 comments It's about queues insofar as the input stream is a queue. So, it's a degenerate case.

thebick + 0 comments Don't need integration, minima, or any such. Don't even need a queue or container, really.

Either the problem is solvable or it's not -- but the problem statement doesn't leave room for unsolvable.

Thus assuming it's solvable, and you're looking for the lowest index from which it works, vinay_star_lord's solution (which I came up with on my own) works

*without*a container, i.e., constant space.mk9440 + 0 comments Simple Array operation :

public class Solution { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int litr[]=new int [n]; int km[]=new int [n]; long cap_value[]=new long[n]; for(int i=0;i<n;i++){ litr[i]=in.nextInt(); km[i]=in.nextInt(); cap_value[i]=(litr[i]-km[i]); } int pos=0; for(int i=0;i<n;i++){ long ptl=0;int check=0; for(int j=0;j<n;j++){ ptl+=cap_value[(j+pos)%n]; if(ptl<0){++pos;check=-9;break;} } if(check==0){System.out.print(pos);break;} } } }

nickdu + 4 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.

#include <iostream> using namespace std; int main() { 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; }

cyanide + 2 comments According to your algorithm if we supply the following output 4 2 1 1 4 2 2 1 1

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.

nickdu + 1 comment 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?

Kartik1607 + 0 comments 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. :)

setusrijan + 0 comments same doubt

kapploneon + 1 comment The problem does not require Queue structre to use but the logic/understanding of the queue helps in breaking down the solution.

mr_sanat + 0 comments You are right :)

setusrijan + 0 comments According to u passing input 3 1 25 2 1 3 1 answer would be 1,but technically answer should be not possible

saket0565 + 0 comments 1

5 6

3 1

2 4

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).

a_anofriichuk + 8 comments Queue-based solutuon, just in case...

struct gasStation { int gas; int next; }; int main() { int N; cin >> N; queue <struct gasStation> route; for (int i = 0; i < N; i++) { struct gasStation st; cin >> st.gas >> st.next; route.push(st); } int start = 0, passed = 0, gas = 0; while (passed < N) { struct gasStation st = route.front(); gas += st.gas; route.pop(); if (gas >= st.next) { passed += 1; gas -= st.next; } else { start += passed + 1; passed = 0; gas = 0; } route.push(st); } cout << start << endl; return 0; }

Zen_Programmer + 0 comments Thanks a lot man!

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

Snigdha_Sanat + 3 comments 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?

a_anofriichuk + 2 comments 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?

Snigdha_Sanat + 2 comments 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.

ujjwalsaxena + 0 comments I believe there is always a solution.

vishnayak + 0 comments 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.

aishik_swarez + 0 comments [deleted]

aishik_swarez + 1 comment 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

noelkali + 0 comments 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).

Mr_DarkSider + 0 comments 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...!!

theparadoxer02 + 0 comments efficient and clean solution!

ashish_mhetre8 + 0 comments how do u come up with such great solutions?

vsaini93789 + 0 comments It's O(n^2) in worst case.

atique + 0 comments 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,

public class TruckTour { public Queue<int> PPQueue; public void TakeInput() { PPQueue = new Queue<int>(); int n = 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 Pump public int GetStartingPumpIndex() { // start with an initial queue // start index is 0 // keep popping items // whenever it fails forward it to the next tage.. int pass_count = 0; int s_fa = 0; int pp_start_index = 0; while (pass_count < PPQueue.Count) { int r_fa = PPQueue.Dequeue(); // residue of fuel amount s_fa += r_fa; if (s_fa < 0) { s_fa = 0; pp_start_index += pass_count + 1; pass_count = 0; } else pass_count++; PPQueue.Enqueue(r_fa); } return pp_start_index; } }

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

- Calculate the first point from where the truck will be able to complete the circle
- An integer which will be the smallest index of the petrol pump from which we can start the tour.

driftwood + 1 comment ### C++ USERS

**This problem can be completed in O(N) (linear) time complexity using**`std::queue<type>`

;*if you've not utilized*`queue`

when solving the problem, you've not been successful (mind the category that the problem is in...)**HINTS:***- You require only the standard constructor class of*`std::queue<type>`

*- O(N) is possible; you must only iterate through the*`queue<type>`

once*- Mind the size of input variables; set*`type`

accordingly*-*`queue<type>`

's`type`

must make use of`std::pair<type,type>`

GrahamS + 1 comment I used a

`<vector>`

rather than a`<queue>`

, and then just wrapped the index around to make it a circular queue. Still a "queue-based solution" but a bit more efficient than repeatedly pushing and popping elements.struct Pump { int fuel; int distanceToNext; Pump(int f,int d) : fuel(f), distanceToNext(d) {} }; bool getTruckin (vector<Pump>& pumps, int startPump) { int fuelInTank = 0; int currentPump = startPump; while (true) { fuelInTank += pumps[currentPump].fuel; // Fill her up if (fuelInTank < pumps[currentPump].distanceToNext) { // Not enough fuel to reach next pump return false; } else { int nextPump = (currentPump + 1) % pumps.size(); if (nextPump == startPump) { return true; // Completed loop } else { fuelInTank -= pumps[currentPump].distanceToNext; currentPump = nextPump; // Keep on truckin } } } }

jyotsanamall12 + 0 comments hey i used queues too...but i am getting a wrong answer for test cases in which n= 100000. where is this code going wrong. please help!

void queue :: circle() { node *now= front; int Pleft= 0, c= 0, index= 0; node *temp= now, *ptr= now; while(temp->next != now) { Pleft+= temp->petrol; //cout<<"pleft: "<<Pleft<<" distance: "<<temp->dist<<endl; if(Pleft < temp->dist) { temp= ptr->next; now= temp; ptr= temp; Pleft= 0; c= 0; } else { c++; if(c == 1) { ptr= temp; index= temp->petrol; } Pleft-= temp->dist; // cout<<"in else pleft: "<<Pleft<<endl; temp= temp->next; } } int flag= 0; while(front->next != front) { if(index == front->petrol) { cout<<flag<<endl; break; } flag++; front= front->next; } }

vibhor3 + 0 comments So Happy after having solved this via queue and in decent time complexity too :)

vinay_star_lord + 4 comments Easiest approach:

N=input()

sumi=0;

maxi=0;

j=0;

for i in range(N):

`a,b=raw_input().split() sumi+=int(a)-int(b) if(sumi<0): sumi=0 j=i+1`

print(j)

daversm + 0 comments Yup, this seems to be a good one

dst33nburgh + 0 comments [deleted]talluri + 1 comment Can anyone explain the logic behind this program. Thanks.

t_egginton + 2 comments as you move through the list, you sum up the Diff = (fuel-distance). If this value ever drops below 0 then it means you can't start from any point up to this point and still make it past this point. You therefore set the next possible point as the pump after your current one and try again.

parmarabhishek_1 + 0 comments " you can't start from any point up to this point and still make it past this point " how did you fifure out that one

MPrashanthi + 1 comment This was what i wanted to know!!!

zhengyuliang5 + 0 comments Me, as well!!!

maximshen + 3 comments I understand what you are doing here. But suppose you find j as the smallest starting point, your program makes sure there is enough gas to finish the remaining routes from j to N-1, since the route is a circle, but how can you guarantee your gas can cover the route from 0 to j-1 ?

vinay_star_lord + 1 comment Hey, Thanks for pointing it out!! I think this serves it,

public class Solution {

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int N =in.nextInt(); int sum = 0; int position = 0; int residue = 0; int a,b; int preA=0; int preB=0; for(int i=0;i<N;i++){ a = in.nextInt(); b = in.nextInt(); sum =sum +(a-b); if(sum<0){ residue+=sum; sum=0; position = i+1; preA=a; preB=b; } if(i==N-1){ if(sum+residue>=0){ System.out.println(position); } else{ if(position<N-1){ i=position+1; position=i; sum=0; residue+=preA+preB; } else{ System.out.println(-1); } } } } }`

}

Snigdha_Sanat + 0 comments Hey Vinay, can u try for this test case?

7

5 2

1 2

3 3

2 6

6 2

2 2

3 6

ujjwalsaxena + 0 comments Its not mentioned. We can assume there is always a solution for this problem

Imvishalsr + 0 comments Hi maximshen. There is no point going back to 0 to j-1 because you already know they can't be the starting point as they already have failed. However, it will be useful to know if they cant have a starting point since there is not enough fuel to complete the circle no matter where you start. But I believe all the test cases have solutions. So, there is really no need to bother about 0 to j-1.

cpu_meltdown + 1 comment I don't really get this yet. The goal is to make the truck start at the pump which will make it travel the least distance? but what does the statement "The truck will move one kilometer for each litre of the petrol." means?

CodeBoyS2 + 0 comments Goal is to find the first petrol station on the circle starting from which the truck will have enough fuel to compelte the circle and get back to starting point.( truck gets to refuel at every station).

karthikeyankc91 + 1 comment We have done it in O(n) whithout any extra memory.

static int truckTour(int[][] petrolpumps) { long sum = 0; int index = 0; boolean isIndexSet = false; for (int i = 0; i < petrolpumps.length; i++) { int currFuel = petrolpumps[i][0]; int currDist = petrolpumps[i][1]; int diff = currFuel - currDist; sum += diff; if (sum < 0) { isIndexSet = false; sum = 0; } else { if (!isIndexSet) { isIndexSet = true; index = i; } } } return index; }

mashkur002 + 0 comments Super Code....

rohit_bokam97 + 0 comments q = [] n = int(input()) temp = 0 for _ in range(n): f,d = map(int,input().split(' ')) temp = temp + (f-d) q.append(temp) pos = q.index(min(q)) if pos == n-1: print(0) else: print(pos + 1)

Sort 119 Discussions, By:

Please Login in order to post a comment