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 : )

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 y on 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, and v2) 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 that v2 < v1 is true. If this evalutes to false then 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:

1. you got a whole number greater than zero
2. you got a fractional number greater than zero

In scenario one, this means that after y jumps, 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) == 0 and 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);

Hello friends,

This problem can be solved in O(1) time by using simple mathematics.

If interested to know more about this algorithm in details-

click here for the video explanation of generic algorithm with complexity analysis.

or you can click on the image too to follow youtube tutorial.

Here is the working solution with O(1) complexity:-

source code :

static String kangaroo(int x1, int v1, int x2, int v2) {

		if (v1 > v2) {
			
			int remainder = (x1 - x2) % (v2 - v1);
			
			if (remainder == 0) {
				return "YES";
			}
		}
		return "NO";

	}

Would really appreciate your feedback like, dislike , comment etc. on my video.

Do not forget to upvote, if you find it useful.

Explaining (x2 - x1) % (v1 - v2) == 0

On the default example 0 3 4 2 I began by picturing K2 was ahead but not moving.

k1  - - - k2
x=0       x=4
v=3       v=0

Now we just have to see if K1 will land on 4 as it hops by.

This is a simple matter of whether v1 is a factor of 4 (clearly it will jump over it):

(x2 - x1) % v1 = (4-0) % 3 = 1

Imagine the alternative case where K2 is also moving: v2 = 2

If v1 > v2 we know v1 will eventually catch up. If on each jump K1 advances 3 steps and K2 advances 2 steps, then K1 is gaining on K2 by 3 - 2 = 1 each jump (each jump they'll be 1 less apart than the jump before). Now K1 just has to close that original distance (4).

4 6 8 10 12  <- K2
0 3 6  9 12  <- K1
4 3 2  1  0  <- Difference
 1 1  1  1   <- Rate

If the rate at which the distance is closing can add up to the original distance between them (4), you know they'll eventually meet.

Now take the example 3 4 10 2 where they do not meet.

10 12 14 16 18  <- K2
 3  7 11 15 19  <- K1
 7  5  3  1 -1  <- Difference
  2  2  2  2    <- Rate

The rate isn't a factor of the original distance, therefore they will never meet: 7 % 2 = 1

This problem can be solved purely mathematically, without any iteration.

Assume that there exists some k number of jumps, at which they will meet:
x1 + k(v1) = x2 + k(v2)

Solving for k:
k = (x2 - x1) / (v1 - v2)

If k would be a positive integer, they will land at the same location in k jumps.

(Note: If k is negative, they would have to hop backwards. If k is not an integer, they will pass eachother while in the air.)

So you just need to evaluate if that function would result in a positive integer. You don't even need to actually determine a value for k. And no iteration is required.

The code for this is left as an exercise for the reader.