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.
This solution has more or less been posted already, but I thought some further explanation of the underlying equation would be helpful. Basically, instead of any sort of looping, this problem can be solved with some algebra. (the below solution is in JavaScript)
We're given the starting position and jumping distance of two kangaroos. We want to know if these two kangaroos will ever land on the same position in the same number of jumps. We can put this scenario into an equation, where y is the number of jumps:
x1 + y * v1 = x2 + y * v2
The above equation can be phrased as a question: how many jumps does it take for both kangaroos to land on the same spot?
Since we are given all the variables except for y, we can rearrange the equation to solve for y. The below steps turn the equation into a form in which we can easily solve for y:
Given values for the other variables, if y is a positive, whole number, the two kangaroos will be able to meet (and, of course, we now know in how many jumps, and on what point on the number line). We can determine if y is 1) positive and 2) whole in two steps.
We can filter out negative values by simply checking if the second kangaroo, which we know from the problem's stated constraints always starts ahead of the first kangaroo, jumps as afar as or farther than the first kangaroo. In practical terms, we know the kangaroos will never meet if the second kangaroo jumps farther than (or as far as) the first since first would never be able to 'catch up' second. So:
if (v2 >= v1) return 'NO';
Now we convert our solve-for-y equation to determine if y is a whole number. By using the modulo operator instead of the division operator, we can see if there are any remainders from the division. If there aren't any remainders, we know that y is a whole number. So:
if ((x2 - x1) % (v1 - v2) === 0) return 'YES';
Putting this all together, we have nice and neat O(1) time function:
Number Line Jumps
You are viewing a single comment's thread. Return to all comments →
This solution has more or less been posted already, but I thought some further explanation of the underlying equation would be helpful. Basically, instead of any sort of looping, this problem can be solved with some algebra. (the below solution is in JavaScript)
We're given the starting position and jumping distance of two kangaroos. We want to know if these two kangaroos will ever land on the same position in the same number of jumps. We can put this scenario into an equation, where
y
is the number of jumps:x1 + y * v1 = x2 + y * v2
The above equation can be phrased as a question: how many jumps does it take for both kangaroos to land on the same spot?
Since we are given all the variables except for
y
, we can rearrange the equation to solve fory
. The below steps turn the equation into a form in which we can easily solve fory
:Given values for the other variables, if
y
is a positive, whole number, the two kangaroos will be able to meet (and, of course, we now know in how many jumps, and on what point on the number line). We can determine ify
is 1) positive and 2) whole in two steps.if (v2 >= v1) return 'NO';
y
is a whole number. By using the modulo operator instead of the division operator, we can see if there are any remainders from the division. If there aren't any remainders, we know thaty
is a whole number. So:if ((x2 - x1) % (v1 - v2) === 0) return 'YES';
Putting this all together, we have nice and neat O(1) time function: