Let us try to understand this problem statement first. We are in charge of a fancy circus and 2 kangaroos have to jump on a number line. The interesting part is that both the kangaroos have a different start position, and different jump distances. It is a little tricky to understand, the problems asks to calculate the number line jumps such that both the kangaroos are at the same position.
We will try to simplify this using some diagrams, and see how the kangaroos actually jump.
In the given test case, kangaroo 2 starts at position 4, and kangaroo 1 starts at position 0.
The problem also says that kangaroo 2 has a jump distance of 2, and kangaroo 1 has a jump distance of 3. If we check the number line jumps, the kangaroos will be at a different position each after 1 jump.
Jump 1:
Kangaroo 2 reaches the position 6 as it is hopping 2 places.
Kangaroo 1 reaches a position 3 as it is hopping 3 places. The diagram below helps to understand it better.
Jump 2:
Following this strategy, both the kangaroos will have number line jumps. Since kangaroo 1 is faster than kangaroo 2, it is quite evident that at some point of time 1 will overtake 2.
Jump 3:
If we keep following the position of both the kangaroos, we will eventually see that in this case they will meet at some time.
Jump 4:
At jump number 4, both the kangaroos are the the same position on the number line. Hence, the answer to this test case is YES. It could also be possible that kangaroo 1 overtakes kangaroo 2 sometime in the air, or if its speed is less, it may never overtake at all.
In all such cases, we need to return NO as the answer.
Efficient Solution:
The problem can be approached in an efficient way using some basic mathematics. We know the speed of both the kangaroos.
speed = \frac{distance}{time}Based on this we can calculate the total distance traveled by both the kangaroos.
distance = speed * jumps
Let us say the start position of kangaroo 1 is x1, and it’s speed is v1.
Start position of kangaroo 2 is x2, and it’s speed is v2.
Let j be the number of jumps after which both the kangaroos reach the same place. We want to make sure that both the kangaroos are at the same place on number line. Hence we can equate both the distances.
x1 + (v1 * j) = x2 + (v2 * j) \newline x2 - x1 = (v1 - v2) * j \newline j = \frac{(x2 - x1)}{(v1 - v2)}The number of jumps j can only be a in integer, if the modulus of the expression is 0.
(x2-x1) \bmod (v1-v2) == 0
This makes the code really simple.
Code:
String kangaroo(int x1, int v1, int x2, int v2) {
if (v1 < v2)
return "NO";
if ((x2 - x1) % (v1 - v2) == 0)
return "YES";
else
return "NO";
}
Code language: Java (java)Time Complexity: O(1)
Space Complexity: O(1)
You can also find the code and test cases on Github.
Video Explanation:
