Mily94 well, I think it is much easier than we think... We just need solve equation : x1 + y * v1 = x2 + y * v2 where "y" is number of jumps... so if (x1 - x2) % (v2 - v1) == 0 then our kangaroos will meet each other : )
jigarjani Whoa.. Bam!! Didn't think that. Still need to take care of things like zero and negative.
rolfbuch The problem states that x2 is strictly greater than x1.
Thus, if v2 == v1 then the answer is "NO".
Thus, both x2-x1 and v1-v2 are guaranteed positive and non-zero.
Interpretitis The expression (v2 - v1) is not guaranteed to be positive as the speed of the second roo could be greater than the first. However, for a YES solution the expression (x1 - x2) / (v2 - v1) must be a positive integer.
rolfbuch [deleted]rolfbuch [deleted]rolfbuch (Been having trouble submitting comments, sorry if this comes through multiple times. Also, you state v2-v1 is not guaranteed to be positive, which is true. I believe you meant v1-v2, which I address below.)
The problem states that X2 > X1, so if V2 >= V1 then there is no solution.
Therefore, for any data that we will operate on (V1-V2) is guaranteed to be positive.
ibrahimker int k1 = x1; int k2 = x2; if(x2>x1&&v2>v1){ System.out.print("NO"); } else{ for(int i=0;i<10000;i++){ k1+=v1; k2+=v2; if(k1==k2){ System.out.print("YES"); System.exit(0); } } System.out.print("NO"); }ez
Meenachinmay looping 10000 times...dont you think its a brute force like approach i also thought the same idea but didnt apply for the same reason...we can make a logic to solve this nahhhh????
P1zzAdr0hn3 [deleted]mohan_pierce007 function kangaroo(x1, v1, x2, v2) { var difference=0;
var calculate=function(){ if((x1<x2)&&((v1<v2)||(v1==v2))){ return "NO" } else{while(Math.sign(difference)!=-1){ x1+=v1; x2+=v2; difference=x2-x1; if(difference==0){ return "YES" } } return "NO" } }(); return calculate; }
Check the difference between the two kangaroos on each jump if they come to become 0 then yes or no if the difference goes to negative-This is the main logic other anomaly is if both distances are equal from start theyll never produce negative or 0 so print no and see if the second kangaroo is way ahead than the first one from start if yes then print "No"
Javascript
apatial27 good logic
wilpat456 Awesome. To make the code reuseable in cases where x2 isn't guaranteed to be greater than x1, i made some changes; Before the while loop, i added this
var sign = x2 - x1;`if (sign > 0) { sign = -1 } else { sign = 1 }`I then included this sign into the while loop:
while (Math.sign(difference) != sign){...do your logic...}
DavidZhai This is not optimal due to two reasons: 1. you have a minimum of 10,000 loops (which for many problems will take way longer than they need to solve) 2. Suppose it takes 10,001 steps for the kangaroos to be on the same spot. This might not be a mathematically possible case given the constraints, but for a bigger problem size it might. I think in general it is not good to introduce arbitrary large numbers for looping through, given the possibility of potential weird subtle bugs when scaling the code up. (Although of course this is just a practice problem so doesn't necessarily apply).
Given all that, you can still keep most of your code with the change of the for(10000) into a while (x1 < x2). This suggests that once the left kangaroo passes the right kangaroo, they'll never meet because they have fixed velocities. There might be some other subtle changes you need, but this is a good starting point. Good luck!
mohan_pierce007 Will this be optimal?
function kangaroo(x1, v1, x2, v2) { var difference=0; var calculate=function(){ if((x1<x2)&&((v1<v2)||(v1==v2))){ return "NO" } else{ while(Math.sign(difference)!=-1){ x1+=v1; x2+=v2; difference=x2-x1; if(difference==0){ return "YES" } } return "NO" } }(); return calculate; }
Check the difference between the two kangaroos on each jump if they come to become 0 then yes or no if the difference goes to negative-This is the main logic other anomaly(Infinite looping problem) is if both distances are equal from start theyll never produce negative or 0 so print no and see if the second kangaroo is way ahead than the first one from start if yes then print "No"
trungtlt why 10.000??? these kangarooes can jump to infinity, your ans abs can not solve this problem
paul_schmeida Exactly, 10k is the maximum jump distance for 1 jump, there's no limit on number of jumps.
It can be solved by looking for same position at the nth jump until the kangaroo that was behind gets in front of the other. The guy gave the equation in the first comment, after checking for impossible combinations just use that equation.
gkjha009 I did the same, and it worked. No need to run loop in vein.
if( x2>x1 && v2>v1) return "NO";
let result = (x1-x2) % (v2-v1); if( result === 0){ return "YES"; } return "NO";jossdean nice!
i applied the remander (mod %) after calcultion (x2-x1 / (v1-v2) ... your is nice and ismple
AAKASH_SHINGHAL you will just need to add divide by zero error check before checking the modulus., as v2-v1 can give divide by zero run time exception
zarafridi1 It will cause run time error for modulus operation if v1 equals to v2. Can be fix by changing first condition to this:
if( x2>x1 && v2>=v1) return "NO";
rassh1512 let result = (x1-x2) % (v2-v1); can anyone explain this what's happning in this statement?
anoop_ks007 Could u please explain the logic behind (x1-x2) % (v2-v1).
girish_sharma_01 yes you are right.
lindanordstrom86 There is no limit to jumps, BUT there are constraints to their distance between them and jump length, right? So by taking the "worst case" scenario which would be:
x1 = 0
v1 = 2
x2 = 10000
v2 = 1
it will take 10 000 jumps for the first kangaroo to catch up with the other one, any more jumps is impossible under these constrainst, therefor the loop solution is valid.
But, I agree that the "(x1 - x2) % (v2 - v1) == 0" solution is neater ;)
bgreenfield [deleted]
ben_nxumalo you will need to add validation for division by ZERO PHP version that worked for me if((v1 && x2)||(x2 && v2)) return "NO"; elseif(x2 || v2) return "NO"; elseif((x2) % (v1) == 0) return "YES"; return "NO";
NiceBuddy this passed all tests even it runs almost 10K times!
#include <bits/stdc++.h> using namespace std; string kangaroo(int x1, int v1, int x2, int v2) { // Complete this function string Ans="Not yet decided!"; if( (v1>v2 && x1<x2) || (v1<v2 &&x1>x2) ) { for(unsigned int i=0; i<10000; i++) { x1=x1+v1; x2=x2+v2; if(x1==x2) { Ans="YES"; return Ans; } } Ans="NO"; return Ans; } else { Ans="NO"; return Ans; } }
nav293 I passed all testcases and didn't even use a loop.
iylamsriramteja will u send me the code i passed only 19 test cases
nav293 if(v2>=v1 && x1!=x2){ return "NO"; } else{ float x = (float)(x2-x1)/(v1-v2); if( floor(x) == x ) return "YES"; else return "NO"; }
zakiralig184 [deleted]zakiralig184 [deleted]zakiralig184 In constraint it is given that X1 is less than X2, therefore, there is no need to check X1 isn't equal to X2.
ssaulakh2 Can you expalin your code so others can learn?
praveenbisht390 what's floor(x)??
Beeksie It is a method that gives the largest integer that is less than or equal to the argument.
tejaasvenkatesh To check whether (x2-x1)/(v2-v1) is a perfect integer, he considered the float value and floor value of it. Floor gives the number that is less than original number. 15.4 gives 15. -13.2 gives -14
ritzerk When dividing all integers by all integers, you will get an integer. However, only full jumps will count. If they meet mid-jump, it's a No. Therefore, at least one of the integers going into the equation x1 - x2/v2 - v1 needs to become a float.
Then, once the equation returns a float, it may give u a positive result of mid jump, e.g. 5.4 or 6.7.
Since now you are getting something that should return a NO, you need to check if the result is an integer to see if it should be a YES.
Floor (result) is the integer value of whatever float. Therefore, if result == floor(result), then the float must of been an integer in the first place, and so you output a yes.
kashish25798 [deleted]
fimaruf a small correction for this scenario (v2 & x2)
if (v1 && x2) { return "NO"; } else { (float)x2 - v1 - d) == $d) return "YES"; else return "NO"; }
talhamahmood2001 if x1=3, v1=2 and x2=2, v2=3 then it also return "NO" But both kangaroo meet at distance of 5.
kadarsh115 this is absolutely one of the finest logics for this problem. you are awesome man. impressive code
Mumthas_43 I think this is an easier solution N it works for all the cases
if((x1<x2) && (v1<v2)) System.out.println("NO"); else { if((v1!=v2) && ((x2-x1)%(v1-v2))==0) System.out.println("YES"); else System.out.println("NO"); }Wafflenaut By the definition of the problem, x1 is always less than x2 - so no need to test for that in your first if statement. Otherwise it looks good.
ankitmishra7991 [deleted]ankitmishra7991 [deleted]ankitmishra7991 [deleted]
panjama231 - "By the definition of the problem, x1 is always less than x2"
- I don't see where this is stated in the problem.
mauroz771 Look at the first constraint in the statement: 0 <= x1 < x2 <= 10000
panjama231 Okay, thank you.
I will try to pay better attention to the constraints next time.
AngelSolorio @mauroz771 I saw that restriction but in the first example given inside of the description of the problem, x1 = 2 while x2 = 1, so that restriction has not been followed.
danislav_kirov You can do it with only one if-else statement:
if(v1 > v2 && !((x2-x1)%(v1-v2))) printf("YES"); else printf("NO");
This works for all test cases.
jefflima This solution will work for C/C++ because any number other than zero returns false. For Java:
f(v1 > v2 && ((x2-x1)%(v1-v2) == 0)) printf("YES"); else printf("NO");
That will work any case.
omarsamy09 can you explain please ?
arungov i think...
// given that x2 > x1, if v1 > v2 its a NO because kangaroo2 is already behind and cannot catchup by going slower than kangaroo1
// x2-x1 % v1-v2 this basically checks if the diff in the inital lead (x2-x1) can be made up by going faster
wyrlvillazorda why v1 < v2 is always false? can u explain?
karatedog - x2 is always greater than x1 -> the second kangaroo is always ahead of the first kangaroo
- v1 < v2, it means v2 is greater than v1, so the second kangaroo is faster than the first
- conclusion: if the second kangaroo is ahead of the first kangaroo and he is faster, then the first kangaroo can never catch up to the second kangaroo
kencluff Nice!
ammwaheed Can you please explain your algorithm?
bhindekishan99 when v1=v2 and x1=x2 for this case also ouput is "YES"
dai_co how can x1 = x2 if x1 < x2?
cs_nguyenhuudat why v1 > v2 and !(x2-x1)%(v1-v2) can you explain to me, plz! and if the text is (4 2 0 3) at that time v1 < v2 but it still true ??
Beeksie Can you explain why we use (x2-x1)%(v1-v2)? What is the logic behind this?
r_regueiro_sant1 % means module. If the % !== 0 then (x2-x1) the diference between both start points it's not divisible with (v2-v1) the diference of speed then they never will land on the same spot at the same time. 4%2 is 0 5%2 = 1 because 5/2 is 2*2 + 1
anuragccsu The solution is elegant but it assmues that x2 is > then x1 which is not mentioned in the problem and also dont handle the case of v1 == v2 so i modified it:
if ((v1 == v2) && !(x1 != x2)) printf("NO"); if(v1 > v2 && !((x2-x1)%(v1-v2))) printf("YES"); else if(v2 > v1 && !((x1-x2)%(v2-v1))) printf("YES"); else printf("NO");
AngelSolorio @danislav_kirov when the entrance is: kangaroo(x1: 0, v1: 3, x2: 4, v2: 2) should print "YES" and your code actually prints "NO"
ankitmishra7991 [deleted]ervaibhavkumar How this expression come to ur mind ? could u plz explain this expression ((x2-x1)%(v1-v2))==0)
beastieric If the two kangaroos met, then there woulde be an integer n such that x1 + n * v1 = x2 + n * v2. Subtracting x1 from both sides, we get that n * v1 = x2 - x1 + n * v2. Then we subtract n * v2 from both sides and we get n * v1 - n * v2 = x2 - x1. Factoring out n from the left side of the equation, n * (v1 - v2) = (x2 - x1). We can the divide both sides by (v1 - v2) and we get (x2 - x1) / (v1 - v2). If this is an integer, then (x2 - x1) % (v1 - v2) has to equal 0.
egarcia405 is n considered to be the same amount of jumps both kangaroo take?
IMCorey Yes. That's exactly what we need, the 'n' to be the same for both, so yes, n refer to the both kangaroos jump.
ibarry @beastieric. You are a beast. God Bless You!
marcusalexander thanks for the explanation. it helped me alot
sminmgr If this is an integer, then (x2 - x1) % (v1 - v2) has to equal 0. Can you explain this statement, I didn't get it.
karatedog "%" is the modulo operation, not division. When the modulo is 0, it means that dividing (x2 - x1) by (v1 - v2) has no remainder -> that is: (v1 - v2) can divide (x2 - x1) by a whole number of times.
sminmgr Oh thanks
edwinjo466 thanks @bosteric
shubham4230 If the two kangaroos met, then there woulde be an integer n such that =>x1 + n * v1 = x2 + n * v2 =>n * v1 = x2 - x1 + n * v2 =>n * v1 - n * v2 = x2 - x1 =>n * (v1 - v2) = (x2 - x1) =>n=(x2 - x1) / (v1 - v2) If this is an integer, then (x2 - x1) % (v1 - v2) has to equal 0.
victorkurauchi nice explanation! one thing i noticed running the tests was that with this input 0 2 5 3, the v1 - v2 is negative so we should consider that
if (v1-v2 > 0 && (x2-x1) % (v1-v2) == 0) { console.log('yes'); }
bthompson4163 That worked for me, I initially did the while loop way, and then got timeouts, so was trying to think of another way before coming to the discussion. I knew it would have to have something to do with some comparison having a modulo == 0, just couldn't quite get the equation.
kharatpriyank Thank you!
dheepthisb Thank you for the explanation!
tanmay777 Lovely Man!
arvindj19962014 Great explanation.. thanks a lot
sharma486 great solution.
djangodude what does this ((x2-x1)%(v1-v2) == 0) do? can you please explain?
beastieric This statement checks if x2-x1 is divisible by v1-v2.
shubham4230 If the two kangaroos met, then there woulde be an integer n such that =>x1 + n * v1 = x2 + n * v2 =>n * v1 = x2 - x1 + n * v2 =>n * v1 - n * v2 = x2 - x1 =>n * (v1 - v2) = (x2 - x1) =>n=(x2 - x1) / (v1 - v2) If this is an integer, then (x2 - x1) % (v1 - v2) has to equal 0.
fanjavaid What is n means?
tincumagic n is the number of jumps until kangoroos meet
weitzhandler Checking for
x1<x2is redundant, it's one of the problem's constraints.
bug_lover I think that in if((x1
nimish_gupta @Mumthas_43 how did you get this logic.
shoelessLawrence Well YES -> Mumthas_43!
static string kangaroo(int x1, int v1, int x2, int v2) { // Complete this function string _return = "NO"; if (v1<v2) { ; } else { if((v1!=v2) && ((x2-x1)%(v1-v2))==0) { _return = "YES"; } } return _return; }
sanjay311999 Still the code can be trimmed like this
if(v1<=v2) cout<<"NO"; else { if((x2-x1)%(v1-v2)==0) cout<<"YES"; else cout<<"NO"; }
maheshm121 can you please explain why (x2-x1)%(v1-v2)==0
sliu8 This is in fact wrong. If a was ahead of b even with a lower speed a and b could be at the same spot.
ravi_4800 ryt..i'ts an easier soln
pavanmurgan if i give x1 = 0, v1 = 1, x2 = 0, v2 = 1 this solution fails
shubham4230 given in the question x2 is strictly larger than x1( i.e x2 > x1)
prudhvi1 what if the case x1=x2 and v1=v2
NiceBuddy yes you are right: my program gives for this NO which is not correct. I do nt know then how it passed all cases!
if(x1==x2 && v1==v2) { Ans="YES"; return Ans; }
well adding this will cover that case too. and this time as well I passed all test cases! https://www.hackerrank.com/challenges/kangaroo/submissions/code/61681975
Zinuxs_Torvalds As the problem states a Constraint that x1<x2(in all the possible test cases),I didn't take that case into consideration and btw if x1!=x2 then for both the kangaroo to be at the same postion at the same time it is obvious that v1>v2(or take it as v1!=v2 as the if condition will look after v1<v2).Hope I sloved your query!!
shubham4230 See the constraints X2>x1(always)
johnmensah python version. slightly similar but different
def kangaroo(x1, v1, x2, v2): if((x1>x2 and v1>v2) or (x1<x2 and v1<v2) or (v1-v2)==0): return "NO" if((x1 - x2) % (v2 - v1)) == 0: return "YES" else: return "NO"
apatial27 great
arorarishabh607 it isn't working with 0 3 4 2
balaveer Hey Mumthas_43, how did u arrived at this formula .... ( ((x2-x1)%(v1-v2))==0) , i mean u r not doing any jumps
19soumikrakshi96 Your logic is wrong. The correct brute force approach is: import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
public static void main(String[] args) { Scanner in = new Scanner(System.in); int x1 = in.nextInt(); int v1 = in.nextInt(); int x2 = in.nextInt(); int v2 = in.nextInt(); int c=0; int k1 = x1; int k2 = x2; if(x2>x1&&v2>v1) System.out.print("NO"); else { for(int i=0;i<10000;i++) { k1+=v1; k2+=v2; if(k1==k2) { c++; break; } } if(c!=0) System.out.print("YES"); else System.out.print("NO"); } }}
Sufiyan As mentioned in other answers, the number of jumps are infinity. X-axis is of infinity. We can't limit it to 10000.
uebu_nogami Yes, we can: the initial distance between kangaroos is at most 10000, and each jump makes them at least 1 'distance-unit' closer (if not, they will never meet anyway, this means that the speeds are 'not good').
(But I was too lazy to write the loop instead of doing simple math ^_^)
karadeniz I think it's better if your first if statement contains v2>=v1 instead of v2>v1. When v1 == v2 there is no need to calculate anything because kangaroo1 is always behind, they never catch each other.
iamuday good logic
Appurba x1, v1, x2, v2 = map(int, input().strip().split()) count = 0 for i in range(10000): if v2> v1: break
x1 += v1 x2 += v2 if x1 == x2: print('YES') count += 1 break if x1 > x2 : breakif count == 0: print('NO')
A_Pushpendra if second case i.e x1>x2 is true , considering initially x1
surya_palla1 Good logic bro , i missed the second no case
niveditha_v this works and not x1<10000 or x2<10000 , dont know why !
if(x1>x2 && v1>=v2) cout<<"NO"; else { for(;x1<100000000,x2<100000000;x1+=v1,x2+=v2) { //cout<<x1<<'-'<<x2<<endl; if(x1==x2){ f=1; break;} } if(f==1) cout<<"YES"; else cout<<"NO";
arjun1321 because that condition is only for initial position, not for final position. the final position can be greater than 10000
princevishal14 [deleted]prikshits100 very good
akarsh22 looping it till 10000 is not a solution as for large dataset it can take more than that
if(v1>v2 && x1>x2 ) { System.out.print("NO"); } else if(v2>v1 && x2>x1) { System.out.print("NO"); } else { if((v1!=v2) && ((x2-x1)%(v1-v2))==0) System.out.println("YES"); else System.out.println("NO"); }
schordia The condition I used for the for loop was
for(int n = 1; !((v1>v2 && n*v1 + x1 > n*v2+x2)|| v1
The reason for this is that if the greater velocity has already exceeded the smaller velocity in distance there is no way the smaller velocity can ever catch up or meet the greater velocity. However, some of the test cases timeout because of this condition.
Xedinaska Oh...typical java-developer solution :)
Guys, just remember that answer anytime you think "wtf, why this java app so slow" or "where is my f**ng RAM??!"
dhingra_shubham1 That's racist.
wyrlvillazorda same with me,..
MikeJM In mathematical proof, even if 1 billionth case passes, that doesn't mean the next one will pass for sure.
_yash_agarwal_ you can use while loop.it is much more effective than 10000 iterations.. OR you can loop until x1 is greater than x2.
if(v2>=v1) { cout<<"NO"; } else { while(x1<=x2) { x1+=v1; x2+=v2; if(x1==x2) {cout<<"YES"; flag=1;} } if(flag==0) cout<<"NO"; }
masoumeh_jafari1 I think it is better to solve it this way:
string kangaroo(int x1, int v1, int x2, int v2) { // Complete this function // x1+m*v1=x2+mv2 => m=(x1-x2)/(v2-v1) , m is steps and //m should not be negetive and //remainder should be zero int x=x1-x2; int v=v2-v1; if(v!=0){ if(x%v==0 && x/v>0){ return "YES"; }else {return "NO";} }else {return "NO";} }
It works
Shakil335 Thanks . It works.
static String kangaroo(int x1, int v1, int x2, int v2) { // Complete this function String result1=""; int c=0; if(x2>x1 && v2>v1){ result1= "NO"; } else{ for(int i=0;i<4;i++){ x1=x1+v1; x2=x2+v2; if(x1==x2){ c++; break; } } if(c!=0){ result1="YES"; } else{ result1="NO"; } } return result1; }
This is my code it cant passes 4 test cases . So what is the problem .Can anyone explain?
straho1111 [deleted]
s28_170040431 CORRECT OR WRONG
vivu493 This is Einstein's works.
zakiralig184 C src code without using for loop scanf("%ld%ld%ld%ld",&x1,&v1,&x2,&v2); if(v2>=v1) printf("NO"); else { ((x2-x1)%(v1-v2)!=0)?printf("NO"):printf("YES"); }
It has PASSED ALL TEST CASES. It will control time complexity.
surendraps007 Are you checking the number of jumps also should be equal I did not find any jump condition in your code.
yashpatel7025 for(i=1;((v1>v2 && av1 && b
django_ let it go type of solution!
saininavn007 USE THIS NO NEED FOR LOOP UPTU 1000 OR MORE.... string kangaroo(int x1, int v1, int x2, int v2) { int k=v1; int l=v2; int sum1=v1+x1; int sum2=v2+x2; while(1) {
if((sum1>sum2)&&(v1>v2)) return "NO"; else if((sum2>sum1)&&(v2>v1)) return "NO"; else { if(sum1==sum2) return "YES"; else { sum1=sum1+v1; sum2=sum2+v2; } }}
}
panditaritvik if it is a hit then it will exit the loop, but in case it is not a hit it will be calculating it for a very long time which is not at all optimized.
B_R_A_T_WOLF how we'll make sure that the kangaroos had made same no.. of jump...???
aivi9891 Thaank you sooo much on that!!!
maximshen Incorrect. (v1-v2) is NOT guaranteed positive. You still need to check if (x2 - x1)/(v1 - v2) or just v1 > v2 is positive to print out "YES"
abhishek_cs @maximshen, why do we need to check this condition(x2-x1)/(v1-v2) if we initially find out that v2≧v1 and there is no solution. lets undarstad this with example: take minimum value of x1 i.e, x1=0 so we can take x2=1 because according to problem statement x2 is always greater than x1. now if v1 and v2 bothe are equal then x1 will never catch x2 because of same speed, in this case no solution and print "no". so we can proceed further for solution, only when v2 is less than v1, hence v1-v2 is always positive integer. so there is no need for cheking (x1-x2)/(v1-v2).
mokshjackson100 Where it is stated that x2>x1?
beastieric In the constraints.
panjama231 "The problem states that x2 is strictly greater than x1."
I see no evidence for this. I've read through the problem multiple times.
pratik9044536615 [deleted]
Anuj009 Absolute value should take care of the negatives.
plmuon Yes there are a number of conditions to check:
int num = x2 - x1; int den = v1 - v2; if (den == 0) cout << "NO"; else if (num % den != 0) cout << "NO"; else if (num > 0 && den < 0) cout << "NO"; else cout << "YES";
If x1 < x2 would not be stated, there are just two more conditions to check:
if (num == 0) cout << "YES"; else if (den == 0) cout << "NO"; else if (num % den != 0) cout << "NO"; else if (num < 0 && den > 0) cout << "NO"; else if (num > 0 && den < 0) cout << "NO"; else cout << "YES";
TimSylvester Doesn't handle the case where 2 starts ahead and 1 never catches up (e.g., 0 2 5 3). You need to ensure that the sign of the position difference and the sign of the velocity difference are opposite, i.e., the velocity will overcome the position difference rather than increase it:
print("YES" if (x2 - x1) * (v2 - v1) < 0 and (x2 - x1) % (v2 - v1) == 0 else "NO")This also short-circuits a divide-by-zero error if the velocity difference is zero (e.g., 43 2 70 2).
ShubhamRRathi What is the logic (physics) behind this (x2 - x1) * (v2 - v1) < 0 condition?
wasazimbo I do a precheck for the condition where the kanagaroos travel at the same speed but at different locations (i.e. if(x1 > x2 && v1 > v2) or if(x2 > x1 && v2 > v1)). Beyond that I'm having logic errors when it comes to testing their convergence point.
abhishek_cs according to the problem statement x1 will never be greater than x2 then why do we need to check (x1>x2).
abhi195 ->Product (x2-x1)*(v2-v1) would be >0 when one kangaroo starts ahead of another kangaroo and with greater velocity then another kangaroo. In that case another kangaroo will never be able to catch up.
->Product (x2-x1)*(v2-v1) would be =0 when,
1)Both start with same location but different speed.
2)Both start with different location but same speed.
in either case they will never meet.
eg. 0 5 3 10
(x2-x1)*(v2-v1)>0 First kangaroo will never be able to catch up.
So what we require is (x2-x1)*(v2-v1)<0.
poyrazus Check (v2 < v1) instead of (x2 - x1) * (v2 - v1) < 0 because (x2 - x1) is always greater than zero (given in constraints). Thus;
System.out.println((v2 < v1 && (x2 - x1) % (v2 - v1) == 0 ) ? "YES" : "NO");
lduran This is the best solution
shabeena18 good one!!
koneru_harsha499 can anyone explain the logic behind..... (x2-x1)%(v2-v1)==0
anonymous0169 solving the equation mentioned above, x1+ y*v1=x2+ y*v2 , we get (x1-x2)/(v2-v1)= y . Since y is number of jumps so it has to be an integer. thus (x2-x1)%(v2-v1)==0
maniksrr how (x1-x2)changed to (x2-x1)?
acm_liu11 [deleted]
adi_bhutani16 x1+y*v1 = x2+y*v2
=>(x1-x2)+y(v1-v2) = 0
=>(x1-x2) = -y(v1-v2) Removing the '-ve' sign from RHS =>(x2-x1) = y(v1-v2)
=>(x2-x1)/(v1-v2) = y ----(1)
If you multiply -1 to both the numerator and denominator, then
=>(x1-x2)/(v2-v1) = y ----(2)
Thus equation (1) and (2) are the same.
NanthithaShankar Because it is stated that X2 is always higher than X1 in the problem.
cosmosh remainder is non terminating , ex= value of pi
ashishgulati21 relative velocity concept...if time of seperation of approaching is zero then bothare at same location at a particular time
md_nurezaman What if x2=x1 and v2=v1 ??
koneru_harsha499 both will meet at first jump....so yes will be answer
md_nurezaman But not according to the logic given by @TimSylvester. Isn't it?
abhisheksn Violates the question condition of x2>x1
md_nurezaman Sorry didn't notice that. My bad
kushssj [deleted]abenkalv Can you please explain how did you do (x2 - x1) * (v2 - v1) < 0?
yoleg First you need to solve for y where there is no remainder as discussed above.
Then you need make sure the velocity is correct in that one of the kangaroos will eventually catch up to the other kangaroo.
// javascript solution var remainder = (x1 - x2) % (v2 - v1) == 0; var properVelocity = ((x1-x2 > 0) && v2 > v1) || ((x1-x2 < 0) && v1 > v2); return remainder && properVelocity ? 'YES': 'NO';
twknab This is a really great solution -- thanks for sharing this -- nice and clean!
yashpatel7025 thanks twknab
Khushboo_Watwani can you please explain, how the value of "y" is calculated...
wasazimbo I found y didn't really need to be calculated if using a loop that performs the x1+v1 and x2+v2 calculation at the same time. That way you can do a simple check at the beginning of each calculation to see if their positions are equal
pc_leo I am using the same method but what should be the condition of the loop? some of my test cases are failing...
thaihocmap123 it is too perfect !!!!
ManoRanjithK Simpler than my algo..Thanks for sharing.. Thumbs Up !!
srachel27 on theory if (x1 - x2) % (v2 - v1) == 0 is good, if v2-v1 equal to one will fail, and if condition is if (v1 == v2 && x1 != x2) or (x2 > x1 && v2 > v1) or (x1 > x2 && v1 > v2) then don't need waste time calculate it, the answer will be no
rajatcube Hello umm i solved it in a different way using arrays but it was way more tedious than this mod(%) thing. I just checked it out and it works much much much better than mine. Its just that how did u get to that thing. I mean did u read any formulae or anything coz i really wanna get this. Just a little background i have been coding since 2 months(I am a first year student and have learnt java in my school and thats all) and I am practicing after one whole year . So i would be grateful if someone really guide me on this. Thanks in advance :)
beastieric If the two kangaroos met, then there woulde be an integer n such that x1 + n * v1 = x2 + n * v2. Subtracting x1 from both sides, we get that n * v1 = x2 - x1 + n * v2. Then we subtract n * v2 from both sides and we get n * v1 - n * v2 = x2 - x1. Factoring out n from the left side of the equation, n * (v1 - v2) = (x2 - x1). We can the divide both sides by (v1 - v2) and we get (x2 - x1) / (v1 - v2). If this is an integer, then (x2 - x1) % (v1 - v2) has to equal 0.
anonymous0169 [deleted]dredd wrong for given case( 0 2 5 3) and many others....
mssrivathsan The condition should be (V2 < V1) && (X2 - X1) % (V1 - V2) == 0 :)
sgaweda I knew something was missing and it took me until here in the comments to actually understand what it was.
Meenachinmay not true,,,,,,,
lalitha1729 in second case :0 2 5 3 in this case x1=0,x2=5,v1=2,v2=3 so (x1 - x2) % (v2 - v1) == 0 as -5%1==0, so this is not correct
wangfuqing80 Yes we just need a couple of check cases to deal with negatives and zeros
kiamottullah why y is same for two jumps ? why not y1 y2 ?
dev_dibyo Because if one kangaroo takes a jump , the other one would have also taken as both jump at same time . So number of jumps for a paticular period of time remains the same . Hence , y is same for both cases .
SmartJavaGeek What if (v2-v1) == 1? For example, if x1=0, v1 =3 , x2 = 100 and v2= 4, will each other meet?
beastieric No, because the 2nd kangaroo started ahead of the 1st one and will keep getting more ahead. However, this is not because v2 - v1 = 1. This is because x1 - x2 is negative while v2 - v1 is not, so it would take negative steps to get there, which can't happen.
jacob0306 112 9563 8625 244 this is one of the test case and according to your logic the answer will be NO instead of YES which is the right answer!
Sojanya Can you provide the name of the equation which you applied and solved? How can I learn about this... Please any link from wikipedia or any other website if possible.
jacob0306 public static void main(String[] args) { Scanner in = new Scanner(System.in); int x1 = in.nextInt(); int v1 = in.nextInt(); int x2 = in.nextInt(); int v2 = in.nextInt();
if ((v1 == v2) System.out.println("NO"); else if (((x1 - x2) % (v2 - v1)) == 0 && ((x1 - x2) / (v2 - v1)) > 0) { System.out.println("YES"); } else System.out.println("NO"); }Let me explain how I do it. Let y1 be the total amounts of jumps that kangaroo 1 does so we have:
x1 + y1*v1 = S1, the distance that kangoroo 1 will get to after jumping y1 times.
Similarly, x2 + y2*v2 = S2, the distance that kangoroo 2 will get to after jumping y2 times.
Question: Given the starting locations and movement rates for each kangaroo, can you determine if they'll ever land at the same location at the same time?
so it means they will meet when S1 = S2 => x1 + y1*v1 = x2 + y2*v2, now we assume that both kangaroo did the same jump then met each other at the same location so the equation now is
x1 + y*v1 = x2 + y*v2 <=> y = (x1 - x2)/(v2 - v1) now can you guess what is the condtion for y is base on the above equation?
that is how I understand it but I may be wrong and sorry for my bad explaination, English is not my first lanquage.
jessibird Using this algorithm and additional tweaks, here is the python 2 code:
if v2 > v1 and x2 > x1: print "NO" elif x1 > x2 and v1>v2: print "NO" elif x1 != x2 and v1 == v2: print "NO" elif (x1-x2)%(v2-v1) == 0: print "YES" else: print "NO"
shivammutreja25 Hey Python buddy! You don't need to check whether x2>x1, it's already given in the constraints.
This should work. Cheers!
if v1 > v2 and (x2-x1)%(v1-v2) == 0: print "YES else: print "NO"
supunrajasinghe how can you solve these equation? please can you explain it.
alison_thaung Let n = number of times each kangaroo hops to eventually land at the same exact distance. To see whether that does happen we need the following expression to be true:
x1 + (v1 * n) = x2 + (v2 * n)
We can check this by looking at the sample input 0, 3, 5, 2 for x1, v1, x2, v2 respectively.
0 + 3n = 5 + 2n n = 5
This means it takes the kangaroos jumping 5 times to land at the same distance:
0 > 3 > 6 > 9 > 12 > 15
5 > 7 > 9 > 11 > 13 > 15
Now that we know the equation is right, let's move n to one side:
(v1 * n) - (v2 * n) = x2 - x1
n(v1 - v2) = x2 - x1
n = (x2 - x1) / (v1 - v2)
We don't know what the value of n will be, but we know that it must be an integer. If the division solves for a whole integer, we know there is no remainder value. So, we use modular division
(x2 - x1) % (v1 - v2) == 0 (meaning no remainder value, and therefore the division solves for an integer)
joseph_mawer How did you know to use the expression x1 + (v1 * n) = x2 + (v2 * n)?? What area of math is this from? What is the name of this expression?
Zarif123 These are linear equations, you usually see them as y=mx+b. Here x1 is b and v1 is m.
hacker_y4s853t8 The equation is an equality to find if there is some value n (number of jumps) such that:
x1 + (v1 * n) = x2 + (v2 * n)
Or in english:
Is there a number N such that
Kangaroo one's position + (it's velocity * N) == Kangaroo two's position + (it's velocity * N)
Where N = the number of jumps
deadfire19 Java8 1 line:
int b = in.nextInt(); int a = in.nextInt(); int d = in.nextInt(); int c = in.nextInt(); System.out.println( b == d || (a-c) != 0 && (((d-b) / (a-c))*a)+b > Math.max(b, d) && ((b-d) % (a-c)) == 0 ? "YES" : "NO" );
Ardillo 1 line?
4 lines for input reading and the lenght of the println is higher than the maximun allowed by the standards so this final line needs to be splitted into two.
4 + 2 is 6 lines not 1.
shad0w99 But do the nummber of jumps need to be the same for both the Kangaroos? I feel that x1+a*v1=x2+b*v2 relates more closely to the problem. Thoughts?
DearVolt I agree - It would be a cooler question. The question does have this note though:
"Note: The two kangaroos must land at the same location after making the same number of jumps."
vikihacksys but what is the limit of y? how to identify the limit of jumps from the given problem?
SreeHarsha_K public static void main(String[] args) { Scanner in = new Scanner(System.in); int x1 = in.nextInt(); int v1 = in.nextInt(); int x2 = in.nextInt(); int v2 = in.nextInt(); int a = x1 - x2; int b = v1 - v2; String res = "NO"; if(a*b < 0 && a%b == 0){ res = "YES"; } System.out.println(res); }
mhlaskar1991 Please explain a bit more.
prashant_pal1212 i think this will help....
include
include
using namespace std;
int main(){ int x1; int v1; int x2; int v2; cin >> x1 >> v1 >> x2 >> v2; if((x1>x2&&v1v2)){ double remainder; remainder = abs(x1-x2)%abs(v2-v1); if (remainder==0.0){ cout<<"YES"; return 0; }
} cout<<"NO"; return 0;}
WittyNotes Yup. Producing a solution like this...
int num = x1 - x2; int den = v2 - v1; System.out.println((den == 0 || num % den != 0 || num/den < 0) ? "NO":"YES");
prakhar_mishra Yup. cracked that !
paridhi_pk7 The case test 10 is giving a runtime error, else if quite fine, tried different codes... even 'v1 = x2 + y * v2 where "y" is number of jumps... so if (x1 - x2) % (v2 - v1) == 0 ' this
DearVolt You need to watch out for when v1 == v2 because then you will try modulus of 0. In this case or the more general case where v2 >= v1, the answer is always NO because the kangaroo just can't catch up.
codebloode_123 good one man
[deleted] Your idea helped me solve this. Thank You! :D
rhpkp really amazing
S_K_Sharma [deleted]jacomatic excellent! this really helped.
styopdev [deleted]aurora19 woahh thank you! i spent so long on this question
defields923 My first attempt was to brute force it with a loop, but JS will timeout. I came to a similar conclusion to fix it, though one or two steps less elegant. Nice deduction!
ScienceD What do you guys thing about this? This idea came to me on my own lol!
#include <iostream> using namespace std; /*Kangaroo functions: Kangaroo 1 = v1 * n + c1 Kangaroo 2 = v2 * n + c2 No matter how different c is, kangaroo with biggest speed will always catch up also v*n is more important than c cos v*n has higher degree P.S. I forgot about NOTE ._.*/ int main() { int c1, v1, c2, v2; cin >> c1 >> v1 >> c2 >> v2; // below: division by 0 is bad! int meet_step = v1-v2 != 0 ? (0 - (c1 - c2))/(v1 - v2) : 0; int meet_mod = v1-v2 != 0 ? (0 - (c1 - c2))%(v1 - v2) : 1; if(meet_step > 0 && meet_mod == 0) cout << "YES";// only if step where our kangaroos else // meet is positive AND is an integer, they meet cout << "NO"; //on the ground, not in the air return 0; }
alcides_ticlla this fails for this case
0 3 4 2
the equation states that the kanguru will never match the same point but output is stating that it should collide
for 1: 0 3 6 9
for 2: 4 6
so they will jump for the same x but never at the same time seems like a bug on the problem definition
Zinuxs_Torvalds The iteration is infinite and btw it meets at 12.
padalkars Great!!!. So simple. Thanks.
ben_nxumalo PHP version that worked for me if((v1 && x2)||(x2 && v2)) return "NO"; elseif(x2 || v2) return "NO"; elseif((x2) % (v1) == 0) return "YES"; return "NO";
minLewis Ah so if the difference in origin is divisible by the difference in velocity, then at some point they will meet. Awesome. Had to sketch that one out
bhatushar The condition is working but I don't understand the principle behind the (x1 - x2) % (v2 - v1) == 0 equation. Can anyone help me?
beastieric If the two kangaroos met, then there woulde be an integer n such that x1 + n * v1 = x2 + n * v2. Subtracting x1 from both sides, we get that n * v1 = x2 - x1 + n * v2. Then we subtract n * v2 from both sides and we get n * v1 - n * v2 = x2 - x1. Factoring out n from the left side of the equation, n * (v1 - v2) = (x2 - x1). We can the divide both sides by (v1 - v2) and we get (x2 - x1) / (v1 - v2). If this is an integer, then (x2 - x1) % (v1 - v2) has to equal 0.
DearVolt There's a really nice explanation here: https://www.hackerrank.com/challenges/kangaroo/forum/comments/327371
Codone Actually that didn't strike :-)
krauszrobert92 return v2<v1 && !((x2-x1) % (v2-v1)) ? "YES" : "NO";
Blaze_Hacker Awesome
alihashir4799 "(x1 - x2) % (v2 - v1) == 0" ??. Can you please explain this??
santhosh10dm43 how these maths logics are finding not a good student in maths lol.
HCLarsen I had to add in a line of "return "NO" if v2 == v1" to avoid runtime divide by 0 errors, but other than that, this worked great.
joseph_mawer What equation is this? How did you know to use that equation? Thanks!
sanjay311999 The problem asks whether they will meet at a particular point after same number of jumps. Distance moved after 'y' jumps kangaroo1 d1 = x1 + v1 * y. kangaroo2 d2 = x2 + v2 * y. 'y' must be same for both kangaroos. d1 = d2. x1 + v1 * y = x2 + v2 * y. rearanging the above equation we get y = (x2 - x1)/(v1 - v2). y is number of jumps which must be a positive integer. Therefore which implies that x2-x1 is divisible by v1-v2. This is how the equation has evolved.
deepnath01 [deleted]HimanshuMakhija Nice way to think about it
dhanasing17 can you explain how x1 + y * v1 = x2 + y * v2 is converted into (x1 - x2) % (v2 - v1) == 0
santoshimn1 Wow thatz really brilliant logic!!!
r141938 by this formula i got wrong result
fanjavaid How you can define using this formula? x1 + y * v1 Why x1 must be add by y and multiply by v1?
Thank you
hani_merzouki that a good aproach that i have tried but the problem is that it does not have the notion of time. the problem says that the kangoroos meet at the same time (or after the same number of jumps) and not just meet. im still working on that part if anyone has any ideas :)
ashishgupta2598 Its like Arithmatic Progression. Like we have to find where two Ap meet But please also justify How u take the number of jumps equal?? Take case as 2,6,8..... and 0,3,6,9.....
ashishgupta2598 Also Take the case when number of jumps are not equal
tecnocratay thank you...you just made it easy!
leeoim How did mathematically solve x1 + y * v1 = x2 + y * v2 to (x1-x2)%(v2-v1) == 0?
qvanphong static String kangaroo(int x1, int v1, int x2, int v2) { for(int i = 1; i > 0; i++){ if(x1+i*v1 == x2+i*v2){ return "YES"; }else if(x1+i*v1 > x2+i*v2) { return "NO"; } } return null; }
This will perform infinite loops until kangarooA > kangarooB, the result will be NO. Cuz at the beginning, kangarooA's starting location always less than kangarooB's location. Else, if kangarooA equals kangarooB (as Mily94 formula), the result we be YES. But this isn't optimal code, it take over 1s to show result from execution.
sha3gatto [deleted]joseph_zamora64 bool diff; string out = "NO"; for(int x = 0; x < MAX; x++){ diff = ((v1*x+x1)-(v2*x+x2)) == 0; //cout << ((v1*x+x1)-(v2*x+x2)) << endl; if(diff){ out = "YES"; break; } } return out; here is another way to do it, MAX is 10000 since it will never go above that.sha_coder [deleted]kerak19 [deleted]
beckamjunior7 [deleted]
tjorgais0021 [deleted]ibrahimhadzic45 def kangaroo(x1, v1, x2, v2): if (v2 >= v1 or (x2-x1)%(v1-v2) != 0): return 'NO' return 'YES'We first check if v2 (second kangaroo's jump) is bigger or equal to v1 (first kangaroo's jump) because there's a constraint that x2 (starting position of the second kangaroo) has to be bigger than x1 (starting position of the first kangaroo). It means that for first kangaroo to reach the second one it has to have bigger jump than the second kangaroo. If the second kangaroo has bigger or equal jump, the first will never catch it, therefore the statement is satisfied and we return a 'NO'.
If the first condition is not satisfied, we check if the combination of starting positions and steps makes it impossible for the first kangaroo to reach the second. If it indeed is impossible (if its modulus doesn't equal zero) we again return a 'NO'.
If none of these happen, we return a 'YES'.
generalom1234 I could only think of this bit but thanks for helping brothah... Appreciate it...
if((x2+v2)%v1 == 0) cout<<"YES";
tmcleod07 Not quite. If y is negative your solution can fail, depending on how the '%' is implemented.
generalom1234 but in my case y won't be -ve will it? but in the statement (x2-x1)%(v1-v2) == 0,x2 - x1 and v1-v2 will always be +ve if we r considering the YES statement
generalom1234 basically i can't understand what u r trying to imply here can u be more specific?
tmcleod07 @generalom1234, I was reponding to the original (parent) post. In the original post, if you convert the expressions to floating point and solve for 'y', The kangaroos meet if y is a non-negative integer, otherwise they do not meet.
generalom1234 ohkkk
valentin_lafran1 Hi, I think your equation is wrong ... Actually you take "y" number of jump as a common factor for both kangaroos, but number of jumps will be different for kangaroo1 and kangaroo2 so we should have y1, y2 number of jump for each kangaroo, am I right ?
anshika83299 I really feel stucked up . I am not able to generate mathematical eqns according to the given problem statements. Seriously in need of help.
saininavn007 contact me
saininavn007 follow me ..i will send u code..
anshika83299 yeah thanks for that but i want to learn at a major priority to develop logic like this..
prikshits100 okew.....that's good.... but i hope u enjoyed my code :)
profnandaa Need to however catch the the case where v2 > v1:
function kangaroo(x1, v1, x2, v2) { // x1 + y.v1 = x2 + y.v2 // y = (x2 - x1) / (v1 - v2) // YES if (x2 - x1) % (v1 - v2) == 0 if (v1 < v2) return 'NO' // impossible catch up if (((x2 - x1) % (v1 - v2)) == 0) return 'YES' return 'NO' }
dm_dubovitsky if (v1 <= v2) return 'NO'
cause it also impossible to catch up
ronaldabellano This is brillant. I
abdmajd2 First check if(v1>v2) or else return "NO" because if v1 < v2, the first kangaroo will not caught second kangaroo even at any high values and if this check is false then check (x2 - x1) % (v2 - v1) == 0
if((v1>v2) && ((x2-x1) % (v2 - v1)))
return "YES";return "NO";
This passes all test cases.
ritzerk This is so satisfying. Thank you.
In C++:
float nJumps = (x1 - x2)/(v2 - v1); if ( nJumps == floor(nJumps) && nJumps >= 0 ) { return "YES"; } else { return "NO"; }
spottyspeedster While this works, it works because you know that Kangaroo 2 is ahead of Kangaroo 1, and presumably you've excluded the impossible case (i.e. Kangaroo 2 has a greater jump distance than Kangaroo 1, as noted in the description).
As an enhancement, if you use the absolute values of the difference in position and the absolute value of the difference in jump rates (after excluding the case of the kangaroo in front having a greater jump distance than the kangaroo behind, for which you should immediately return NO), you can have either kangaroo in front of each other and it still works.
ritabrata_saha There is one test case where x1 x2 v1 v2 are decimals .Mod of decimals are different .What about that
vvdavided This needs further explanation but the idea is ok
bowmanpete123 Give this man a medal! Do you have a background in Math?
nurlan_mikayilov This is right but one thing v2 and v1 should be different.
mrgnwatson I think the formula is messing people up on this. I have found that using words, rather than variable names, to be helpful when writing out the problem.
So we have two kangaroos starting at different locations, and jumping forward at different distances. If we want to know where any kangaroo is at any given time, there is an intuitive equation for that:
Kangaroo Position = (Number of Jumps * Distance per Jump) + Starting Position.
We could also write this as:
K = yv + x
such that K = Kangaroo Position, y = Number of Jumps, v = Distance Per Jump, and x = Starting Position.
That almost looks like an equation your teacher went over in algebra that one time you were dozing off:
y = mx + b. I know we are talking about kangaroos here, but in the background we are really just checking to see when two lines intersect.If we have two kangaroos and we want to know when (or if) they will intersect, given their Starting Position and Distance per Jump, the only thing left to solve for is Number of Jumps.
The kangaroos crossing paths essentially means that Kangaroo Position is equal for both kangaroos. Remember the equation up above
K = yv + x? Now that we have two kangaroos, we need to have 2 different equations, and need to determine which value of y (Number of Jumps) can be plugged in to make them equal. So now we have something like this:(y * v1) + x1 = (y * v2) + x2
We need to get
yon one side of the equation, so we will begin reducing it down.(x1 - x2) = (y * v2) - (y * v1)
(x1 - x2) = y(v2 - v1)
(x1 - x2) / (v2 - v1) = y
Luckily, the problem statement gives us the Starting Position and Distance per Jump (
x1,x2,v1, andv2) for each kangaroo. When we plug in these numbers it will tell us how many jumps it would take for the kangaroos to end up in the same spot. But not so fast! We can do a a little work up front to check if the kangaroo that is starting in front is moving faster than the kangaroo in the rear i.e we need to see if Distance Per Jump for the kangaroo in front is larger than the one in the rear. If so, then the one in the back will never catch up. Before we even attempt find an intersection we need to ensure thatv2 < v1istrue. If this evalutes tofalsethen we are done and the lines will not intersect at any point in the future. If the kangaroos started going the other direction then that would be a different story.Anyway, so we plugged the numbers in and we are ready to see how many jumps it will take. At this point there are two scenarios that will occur:
- you got a whole number greater than zero
- you got a fractional number greater than zero
In scenario one, this means that after
yjumps, the kangaroos will be in the same spot.In scenario two, the kangaroos will intersect, but they will be in the air. Kinda cool, but not what we wanted.
Now we get to the part that seems to mess with peoples heads: the dreaded
%operator. Keep reading, and you will see the solution to this problem.SPOILER ALERT
The code below is how we validate that the point of intersection is a whole number.
(x1 - x2) % (v2 - v1) == 0
The
%operator returns the remainder of dividing two numbers. Lets look at an example:x1 = 0 x2 = 4 v1 = 3 v2 = 2 (0 - 4) / (2 - 3) => (-4 / -1) => 4 = y
There is no remainder here. So
(-4 % -1) == 0and the kangaroos will intersect after 4 jumps.So to put it all together, we need to check the Distance per Jump of the kangaroo in front is less than the one in the rear, and that the equation above gives us a positive integer.
String response = "NO"; boolean canCatchUp = (v2 < v1); if(canCatchUp) { boolean willIntersectOnLand = (x1 - x2) % (v2 - v1) == 0; if(willIntersectOnLand) { response = "YES"; } } System.out.println(response);
arguewithplato This is a great writeup, thank you!
jessiepusateri Really great explanantion! Thanks!
rafaele That's a very clear & helpful explanation. Thank you.
gmzdev1986 clever
mathankumar26 very good explanation.Thank you :)
NickWoodward this has got no where near enough love.
where can I get better at recognising these sorts of patterns? or is it just a matter of knowing that when something intersects you have to use y = mx + b ?
eitherway, nice one! (I just cheated:)
if(x1 < x2 && v1 < v2) return "NO"; while(x1 <= x2){ x1 += v1; x2 += v2; if(x1 == x2)return "YES"; } return "NO";
stolenunder1 Intersection is not always in the form of y = mx + b, this is a linear equation involving one variable (the x, or in our case the number of jumps). We could also have a linear equation with 2 variables, we could also have a mixture of linear and non-linear equations (such as an exponential equation and a linear equation and finding their point of intersection).
Honestly the only shorcut is improving upon math, otherwise you'll be limited by trying to remember certain solutions to equations and when to apply them, but you'll rarely know when NOT to apply them, or which ones to apply for a problem that's a bit more complex :(
A bit more explanation for this one, the Kangaroos jump at a linear rate (their veolcity/jump movement never changes, it's always v1 or v2). Therefore we have something along the lines of:
y = velocity * jumps + startLocation
We are already given velocity AND start location for each kangaroo. let's abbreviate using the actual equation variables (x1,x2,v1,v2), we get two separate equations for y (the total distance travelled after J jumps)
- y = v1 * J + x1
- y = v2 * J + x2
We want to set these equal to each other, this would give us a distance that they both share when their J variable's are equal to one another:
v1 * J + x1 = v2 * J + x2
And using our algebra we get the EQ described above in the other posters solution:
v1 * J - v2 * J + x1 - x2 = 0 Which can be written as: J(v1-v2) = x2 - x1 or (x2-x1) / (v1-v2) = J
So given 2 velocity values and 2 starting positions, like 4 = v1 and 2 = v2 and 0 = x1 and 4 = x2, we can evaluate:
- (4 - 0) / (4-2) = J
- 4 / 2 = J
- J = 2 (so at 2 jumps we should intersect)
Showing the values below of the jumps this is right (the far left value is the starting, arrows point to the next jump location):
- 0 -> 4 -> 8
- 4 -> 6 -> 8
And then of course, as the above states, we need to make sure the jump total is a whole number, otherwise we're intersecting in the air. Which is fine, but this problem doesn't really allow that. After all, given any 2 kangaroos if the "BACK" kangaroo is moving FASTER than the one in front of it, they will eventually collide. It's like 2 cars and the one in back is moving faster, if it doesn't slow down it will hit the one in front of it!
pbase Fabulous write-up. Thanks!
tatianaensslin wooohooo needed this thank ya!
mike232 This is a brilliant write up, thanks for this.
borao Thank you!
Thinkster Ruby Implementation:
def kangaroo(x1, v1, x2, v2) return 'NO' unless v2 < v1 (x1 - x2) % (v2 - v1) == 0 ? 'YES' : 'NO' end
Sort 1295 Discussions, By:
Please Login in order to post a comment