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.
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.
(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.
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????
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"
its breaking from the loop IF it finds the answer..
if (k1!=k2)
it will never break out until i >= 10000
which is a waste of memory, if you only need like 200 loops for example. or with all the "test cases" what if you need 20,000 loops?
i have everything inside of a while with 1 if, 2 else if and an else.
Thats it. Then its dymaicaly looping and not static
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!
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"
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.
Just solve the equation x1 + y * v1 = x2 + y * v2 where "y" is number of jumps by moving y to one side and everything else to another. If y is not a fraction then it is possible.
Just solve the equation x1 + y * v1 = x2 + y * v2 where "y" is number of jumps by moving y to one side and everything else to another. If y is not a fraction then it is possible.
actually this is a math problem, so let's look at from that perspective.
let x1, x2 be the starting point. Now v1, v2 represents the jump length right which is metre/jump,
metre/jump * no. of jumps = metre;
so effectively we are calculating if they have a common end point, so x1 - v1 * n = x2 - v2 *n; taking x1 to that side and v2 * n to this side.
we get, (v2 - v1) *n = (x2 - x1)
so n = (x2 - x1) / (v1 - v2)
well remainder of this is going to be zero if x2 - x1 is a multiple of v1 - v2.
Hence it is very simply, but if v1 === v2, then denominator will be zero, so we have to watch out for that condition.
This is great. The wording of the problem wasn't clear. I thought we had to write a loop to continue to check until we got to 10,000. You, however just wrote the logic to check PER iteration. So, we were only writing the check and assuming the calling code would call this method for a given number of time. Am I correct?
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 ;)
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";
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
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.
@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.
% 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
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 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.
"%" 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.
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.
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.
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.
I don't know if you still need the answer, but I can help you.
The positions and velocities are just a representation of straight lines, with positions beyng the y axis intercept (distance) and the velocities remain the rate of change of position through time (x axis).
So in the if statement you check for (1) that the lines actually meet, (2) that, being discrete series of dots and not continuous, they meet in the same spot, (3) add the case in which they have same speed but not same starting position (as without this you'll fail test 10).
1) you want that the "order" of positions (x1 > x2 or viceversa) to be different from the one of the velocities ( v1 < v2), or they'll never meet, so you can implement a "sign" function like -------> math.copysign(1,x1-x2) != math.copysign(1, v1-v2) (or == if you test for a 'NO!')
2)you know that the 2 kangaroos start with a relative distance abs(x1-x2) (like this we cover both cases, where x1 < x2 or viceversa) and at every step (being that v1 != v2, check at (3)) the slower of the two fills up a little piece of the initial gap, which can be represented by abs(v1-v2) (again to cover both cases).
This means that they will either cross their lines of movement or they'll meet in a particular spot. How to find out? If the gap filled up everytime by the slower kangaroo (the one with smaller v) is a divider of the initial gap, then they will meet at one spot, otherwise they won't.
abs(x1-x2)%abs(v1-v2) == 0 ---> 'YES!'
3) you have to add that clause to the statement, otherwise the case where they have same speed but also an initial gap will return a wrong answer (giving 'YES!' when they actually won't meet because the gap never gets filled)
This approach saves up a lot of time and I arrived to that through long thinking (very long)... and right after that I saw you can just equate the formulas for the two lines and find if n is an integer ------> x1 + (n * v1) = x2 + (n * v2)
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");
}
}
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 ^_^)
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.
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.
stringkangaroo(intx1,intv1,intx2,intv2){// 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 zerointx=x1-x2;intv=v2-v1;if(v!=0){if(x%v==0&&x/v>0){return"YES";}else{return"NO";}}else{return"NO";}}
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.
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)
{
@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).
I missed that part too. It's at the end of the question. And to be honest, I didn't quite understand that this was a condition for all of the test cases. That made me lose quite some time.
I known that there was a matemathic way to solve it it a simple operation but I didn't know how.
So, according to this, if x2 is strictly greater than x1, I realized that the distance between the kangaroos decrease for each jump, thus I wrote the following:
Number Line Jumps
You are viewing a single comment's thread. Return to all comments →
Whoa.. Bam!! Didn't think that. Still need to take care of things like zero and negative.
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.
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.
Solved using 2 different type of solutions. It passed all test cases.
Hackerrank - Kangaroo Solution
how the hell is ur soln not going in infinite loop in second case
Constraints. x1 < x2
gotcha :)
(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.
ez
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????
function kangaroo(x1, v1, x2, v2) { var difference=0;
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
good logic
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
I then included this sign into the while loop:
wow good logic
This doesn't work.
Its not looping 10000 times its is breaking from the loop where it finds a answer.
its breaking from the loop IF it finds the answer.. if (k1!=k2) it will never break out until i >= 10000 which is a waste of memory, if you only need like 200 loops for example. or with all the "test cases" what if you need 20,000 loops?
i have everything inside of a while with 1 if, 2 else if and an else. Thats it. Then its dymaicaly looping and not static
string ans = ""; while (1) { x1 += v1;
x2 += v2;
if (v1 >= v2 && x1 > x2) {ans = "NO"; break;} else if (v2 >= v1 && x2 > x1) {ans = "NO"; break;} else if (abs(x1-x2) % abs(v1-v2) != 0) {ans = "NO"; break;} else {ans = "YES"; break;} } return ans;
System.out.print("YES"); System.exit(0); } } System.out.print("NO");
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!
Will this be optimal?
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"
This an alternative to limit the iterations without running for infinity.
Hi,
Your solution is good but you can do this in more efficient way. Have a look on below comment-
https://www.hackerrank.com/challenges/kangaroo/forum/comments/585778
while(x11<=x22) statement was monumental.
why 10.000??? these kangarooes can jump to infinity, your ans abs can not solve this problem
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.
I did the same, and it worked. No need to run loop in vein.
if( x2>x1 && v2>v1) return "NO";
nice!
i applied the remander (mod %) after calcultion (x2-x1 / (v1-v2) ... your is nice and ismple
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
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";
x2 is always greater than x1, check the constraints
let result = (x1-x2) % (v2-v1); can anyone explain this what's happning in this statement?
Just solve the equation x1 + y * v1 = x2 + y * v2 where "y" is number of jumps by moving y to one side and everything else to another. If y is not a fraction then it is possible.
Could u please explain the logic behind (x1-x2) % (v2-v1).
optimal solution is: if( ( x1 < x2 && v1 > v2 ) || ( x1 > x2 && v1 < v2 ) ) { if( abs(x1-x2)%abs(v1-v2) == 0) return "YES"; } return "NO";
Just solve the equation x1 + y * v1 = x2 + y * v2 where "y" is number of jumps by moving y to one side and everything else to another. If y is not a fraction then it is possible.
I'm doing that but when I test it out, it succeeds on all but eight test cases and I'm not sure why.
actually this is a math problem, so let's look at from that perspective. let x1, x2 be the starting point. Now v1, v2 represents the jump length right which is metre/jump, metre/jump * no. of jumps = metre;
so effectively we are calculating if they have a common end point,
so x1 - v1 * n = x2 - v2 *n; taking x1 to that side and v2 * n to this side. we get, (v2 - v1) *n = (x2 - x1) so n = (x2 - x1) / (v1 - v2)
well remainder of this is going to be zero if x2 - x1 is a multiple of v1 - v2. Hence it is very simply, but if v1 === v2, then denominator will be zero, so we have to watch out for that condition.It is possible to get negative number and decimal number as result. To get "YES" only whole positive numbers should be taken in concidoration.
really nice solution . and i have made a slight modification as well to your solution to pass all the test cases.
def kangaroo(x1, v1, x2, v2): #k1=0,k2=0 try: if x2>x1 and v2>v1: return "NO" elif abs((x1-x2) % (v1-v2)) == 0 and v1!=v2: return "YES" else: return "NO" except: return "NO"
python3 for this line, will cause ZeroDivisionError: integer division or modulo by zero: elif abs((x1-x2) % (v1-v2)) == 0 and v1!=v2: return "YES"
use this instead: elif v1!=v2 and abs((x1-x2) % (v1-v2)) == 0: return "YES"
Briliant... I like this. :)
Nice one, Just change it a bit like
it will check for 0 values or nMod1 issue which always returns 0.
Nice logic bro thanks
No need to check x2>x1 beacause its allready given x2>x1
Ya. It does mention that which I realized later. The code will work even without the part you mentioned.
Nice observation though.....
just amend it a little if( x2>x1 && v2>=v1 ) or one of the test cases will fail
How does this really possible,could you explain abit plz
Hi, can you please help me in explaining the logic why did you used mod operator and why you said yes when result is zero
loop in vain. i hope you don't have loops in your veins... if you do i suggest talking to a doctor! :)
This is great. The wording of the problem wasn't clear. I thought we had to write a loop to continue to check until we got to 10,000. You, however just wrote the logic to check PER iteration. So, we were only writing the check and assuming the calling code would call this method for a given number of time. Am I correct?
yes you are right.
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 ;)
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";
In this case they are matching in every move. elseif(x1 == x2 || v1 == v2)
I passed all testcases and didn't even use a loop.
will u send me the code i passed only 19 test cases
In constraint it is given that X1 is less than X2, therefore, there is no need to check X1 isn't equal to X2.
Can you expalin your code so others can learn?
what's floor(x)??
It is a method that gives the largest integer that is less than or equal to the argument.
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
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.
a small correction for this scenario (v2 & x2)
if (v1 && x2) { return "NO"; } else { (float)x2 - v1 - d) == $d) return "YES"; else return "NO"; }
what is meaning of $d?
if x1=3, v1=2 and x2=2, v2=3 then it also return "NO" But both kangaroo meet at distance of 5.
in Constraints given what x1 < x2
this is absolutely one of the finest logics for this problem. you are awesome man. impressive code
@nav293, it failed on the following input
43 2 70 2
nevermind, my bad to forgot = in first if
They added a case where this no longer works, you have to check whether the Kangaroos land on the same spot for your x
what about if x1>x2 ? in the very first statement
I think this is an easier solution N it works for all the cases
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.
Look at the first constraint in the statement: 0 <= x1 < x2 <= 10000
Okay, thank you.
I will try to pay better attention to the constraints next time.
@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.
Yes, that looked odd to me.
not taking this will result your 1st test case fail
You can do it with only one if-else statement:
This works for all test cases.
This solution will work for C/C++ because any number other than zero returns false. For Java:
That will work any case.
can you explain please ?
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
why v1 < v2 is always false? can u explain?
Nice!
Can you please explain your algorithm?
when v1=v2 and x1=x2 for this case also ouput is "YES"
how can x1 = x2 if x1 < x2?
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 ??
Can you explain why we use (x2-x1)%(v1-v2)? What is the logic behind this?
% 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
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:
@danislav_kirov when the entrance is: kangaroo(x1: 0, v1: 3, x2: 4, v2: 2) should print "YES" and your code actually prints "NO"
If you don't care about code readability, yes.
brilliant
How this expression come to ur mind ? could u plz explain this expression ((x2-x1)%(v1-v2))==0)
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.
is n considered to be the same amount of jumps both kangaroo take?
Yes. That's exactly what we need, the 'n' to be the same for both, so yes, n refer to the both kangaroos jump.
@beastieric. You are a beast. God Bless You!
thanks for the explanation. it helped me alot
If this is an integer, then (x2 - x1) % (v1 - v2) has to equal 0. Can you explain this statement, I didn't get it.
"%" 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.
Oh thanks
thanks @bosteric
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.
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
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.
Thank you!
Lovely Man!
Great explanation.. thanks a lot
@beastieric This is the best expalnation..
great solution.
what does this ((x2-x1)%(v1-v2) == 0) do? can you please explain?
This statement checks if x2-x1 is divisible by v1-v2.
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.
What is n means?
n is the number of jumps until kangoroos meet
Checking for
x1<x2
is redundant, it's one of the problem's constraints.I think that in if((x1
@Mumthas_43 how did you get this logic.
Well YES -> Mumthas_43!
Still the code can be trimmed like this
can you please explain why (x2-x1)%(v1-v2)==0
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.
ryt..i'ts an easier soln
if i give x1 = 0, v1 = 1, x2 = 0, v2 = 1 this solution fails
given in the question x2 is strictly larger than x1( i.e x2 > x1)
what if the case x1=x2 and v1=v2
yes you are right: my program gives for this NO which is not correct. I do nt know then how it passed all cases!
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
See the constraints X2>x1(always)
python version. slightly similar but different
hey i have used the same code but my test casr 10 is not getting satisfiesd
Can you explain how did you come up with below formula:
if((x1 - x2) % (v2 - v1)) == 0:
great
it isn't working with 0 3 4 2
Hey Mumthas_43, how did u arrived at this formula .... ( ((x2-x1)%(v1-v2))==0) , i mean u r not doing any jumps
I don't know if you still need the answer, but I can help you. The positions and velocities are just a representation of straight lines, with positions beyng the y axis intercept (distance) and the velocities remain the rate of change of position through time (x axis).
So in the if statement you check for (1) that the lines actually meet, (2) that, being discrete series of dots and not continuous, they meet in the same spot, (3) add the case in which they have same speed but not same starting position (as without this you'll fail test 10).
1) you want that the "order" of positions (x1 > x2 or viceversa) to be different from the one of the velocities ( v1 < v2), or they'll never meet, so you can implement a "sign" function like -------> math.copysign(1,x1-x2) != math.copysign(1, v1-v2) (or == if you test for a 'NO!')
2)you know that the 2 kangaroos start with a relative distance abs(x1-x2) (like this we cover both cases, where x1 < x2 or viceversa) and at every step (being that v1 != v2, check at (3)) the slower of the two fills up a little piece of the initial gap, which can be represented by abs(v1-v2) (again to cover both cases). This means that they will either cross their lines of movement or they'll meet in a particular spot. How to find out? If the gap filled up everytime by the slower kangaroo (the one with smaller v) is a divider of the initial gap, then they will meet at one spot, otherwise they won't. abs(x1-x2)%abs(v1-v2) == 0 ---> 'YES!'
3) you have to add that clause to the statement, otherwise the case where they have same speed but also an initial gap will return a wrong answer (giving 'YES!' when they actually won't meet because the gap never gets filled)
This approach saves up a lot of time and I arrived to that through long thinking (very long)... and right after that I saw you can just equate the formulas for the two lines and find if n is an integer ------> x1 + (n * v1) = x2 + (n * v2)
Thanks! It worked effecientlty.
if v2-v1 =1 then it won't work.
why can you explain bcz according to me it will work!! 8%1=
it works , but not for every cases
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 {
}
As mentioned in other answers, the number of jumps are infinity. X-axis is of infinity. We can't limit it to 10000.
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 ^_^)
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.
good logic
x1, v1, x2, v2 = map(int, input().strip().split()) count = 0 for i in range(10000): if v2> v1: break
if count == 0: print('NO')
if second case i.e x1>x2 is true , considering initially x1
Good logic bro , i missed the second no case
this works and not x1<10000 or x2<10000 , dont know why !
because that condition is only for initial position, not for final position. the final position can be greater than 10000
very good
looping it till 10000 is not a solution as for large dataset it can take more than that
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.
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??!"
That's racist.
same with me,..
In mathematical proof, even if 1 billionth case passes, that doesn't mean the next one will pass for sure.
you can use while loop.it is much more effective than 10000 iterations.. OR you can loop until x1 is greater than x2.
I think it is better to solve it this way:
It works
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?
CORRECT OR WRONG
This is Einstein's works.
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.
Are you checking the number of jumps also should be equal I did not find any jump condition in your code.
for(i=1;((v1>v2 && av1 && b
let it go type of solution!
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 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.
how can you say that before 10000 iterations k1==k2 they may be equal after 10000
how can you terminate loop at 10000,may k1==k2 after 10000
U can use while loop instead of for....
int p=x1,n=x2; if((x1==x2 && v1!=v2) || (x2>x1 && v2>v1) || (x1>x2 && v1>v2)) return "NO"; else { while(p!=n) { p=p+v1; n=n+v2; if(p>n) { return "NO"; } else if(p==n) { return "YES"; } } } return "NO";
To solve this question, you do not need any loop at all. it can be solved in O(1) time
I hope this comment will help you to opmtize your solution further.-
https://www.hackerrank.com/challenges/kangaroo/forum/comments/585778
yeah my friend, doing a loop in this problem is an awfull way to solve it
int k1 = x1; string s1="YES"; string s2="NO"; int k2 = x2; if((x2>x1) && (v2>v1)){ return s2; } else{ while(k1 } return s2; }
Hi,
your solution is good but it can be optimize further.
I hope this comment will help you to opmtize your solution.-
https://www.hackerrank.com/challenges/kangaroo/forum/comments/585778
here it is violating the contraints.. x1 and x2 <= 10000
you can use a while loop too,where condition is x1-x2<=0 and x1=k1,x2=k2. no need to go till 10000 jumps for few test cases.
how we'll make sure that the kangaroos had made same no.. of jump...???
Thaank you sooo much on that!!!
for which
ldiv
,divmod
, etc will be helpful, minding thev2==v1
casea simple approach using python
even works for cases when x2 is not given to be greater than x1.
i think (x1+nv1) = (x2+nv2) is proper answer and v1>v2 so v1-v2>0 so it will be possible tht (v1-v2) is positive..........
take abs(v2-v1)
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"
@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).
i think (x1+nv1) = (x2+nv2) is proper answer and v1>v2 so v1-v2>0 so it will be possible tht (v1-v2) is positive..........
Dude no worries just add Math.abs() there.
Where it is stated that x2>x1?
In the constraints.
It is in the given value constraints 0 <= x1 <= x2 <= 10000
constraint - 0 ≤ x1 < x2 ≤ 10000. so, X2 must be greater than x1, but it is confusing in the provided first example that x1=2 and x2=1
0<=x1><
The Kangaroo 2 is always ahead of 1st one. hence x2 is always greater than x1
What if x2 is less than X1, it'be a NO then?
The first constraint.
its stated in the "Constraints", although theres no point commenting now as its been like 3 years , you proly have figured that much out lol
Actualy im 12 and dont know it honestly
i'm 18 :)
in the constraints!
it's stated in the constraints
see constraints
I missed that part too. It's at the end of the question. And to be honest, I didn't quite understand that this was a condition for all of the test cases. That made me lose quite some time.
"The problem states that x2 is strictly greater than x1."
I see no evidence for this. I've read through the problem multiple times.
check constraints properly
There is a test case in which v1 is equal to v2
I known that there was a matemathic way to solve it it a simple operation but I didn't know how.
So, according to this, if x2 is strictly greater than x1, I realized that the distance between the kangaroos decrease for each jump, thus I wrote the following:
Hi,
your solution is good with detailed explanation which you are looking for
I hope will comment will help you to opmtize your solution further.-
https://www.hackerrank.com/challenges/kangaroo/forum/comments/585778
def kangaroo(x1, v1, x2, v2): if((x1-x2)%(v1-v2)==0 and (x1-x2)*(v1-v2)<0): return('YES') else: return('NO')
v2>=v1 then the answer is "NO"
nice one, so it would look like
if((x1 - x2) % (v2 - v1) == 0 && (x1 - x2) / (v2 - v1) >= -1)
{ return "YES"; }
Solved using 2 different type of solutions. It passed all test cases.
Hackerrank - Kangaroo Solution
Finally someone 5 days ago all these guys are about 3 yrs or older good to see others which are of the same timeline Kudos Mate
every beginer like me refer this soln
here is problem solution in java python c++ c and javascript programming.
HackerRank Number of lines jumps solution
Here is my c++ solution, you can have the explanation here : https://youtu.be/bRVVCCmXN0Y
Absolute value should take care of the negatives.
Yes there are a number of conditions to check:
If x1 < x2 would not be stated, there are just two more conditions to check:
zero rate delta means same rate, so the positions will always be the same distance apart -> "NO"
zero position delta means they start at the same place -> "YES"
(x1 < x2) AND (v1 < v2) -> never catching up -> "NO"
(x2 > x1) AND (v2 > v1) -> never catching up -> "NO"
negative is out of bound as per constraints given
No bro simply use the slope formula which is basically int temp = (x2-x1)%(v1-v2);
if(v1>v2) { if(sum==num||temp=0) { cout << "YES " ; } else cout << "No"; } else cout << " No";
But it will not work if we put( 0 3 1 5 )as input
you can use abs function to get the abolute value;
def kangaroo(x1, v1, x2, v2): try: if(x1>x2 and v1>v2): return "NO" elif(x1