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.
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.
suppose you start from 1, 2, 3, and breaks at 4, removing 1 from the route (starting from 2) only decrease the petro you collect and surely breaks again.
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 ?
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);
}
}
}
}
}
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.
Truck Tour
You are viewing a single comment's thread. Return to all comments →
Easiest approach:
N=input()
sumi=0;
maxi=0;
j=0;
for i in range(N):
print(j)
Yup, this seems to be a good one
Can anyone explain the logic behind this program. Thanks.
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.
" 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
suppose you start from 1, 2, 3, and breaks at 4, removing 1 from the route (starting from 2) only decrease the petro you collect and surely breaks again.
This was what i wanted to know!!!
Me, as well!!!
same here
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 ?
Hey, Thanks for pointing it out!! I think this serves it,
public class Solution {
}
Hey Vinay, can u try for this test case?
7
5 2
1 2
3 3
2 6
6 2
2 2
3 6
Its not mentioned. We can assume there is always a solution for this problem
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.