Number Line Jumps Hacker Rank Question Algorithms

Question

I passed the exercise which has the description below:

This is my code:

private static boolean findPosition(int x1, int v1, int x2, int v2) {
         int n = Math.abs(x1 - x2);
         for(int i = n; i >= 0; i--) {
             if(x1 == x2) {
                 return true;
             } else {
                 x1 += v1;
                 x2 += v2;
             }
         }
         return false;
     }
     

    public static String kangaroo(int x1, int v1, int x2, int v2) {
    // Write your code here
        if( (x1 < x2 && v1 <= v2) || (x2 < x1 && v2 <= v1) ) {
            return "NO";
        } else {
            if(findPosition(x1,v1,x2,v2)) {
                return "YES";
            }
        }
        return "NO";
    }

But when I refer to another post, which also successfully passed the test case, I met a formula : (x2-x1)%(v1-v2)==0

I've been trying to understand how the formula works failed :(

Can anyone help me understand this formula works

Answer 1

The formula can be derived using basic algebra:

You can write an expression for the position of each kangaroo after some number of jumps, j:

p1 = x1 + j * v1
p2 = x2 + j * v2

Clearly if they are at the same position, p1 = p2, so:

x1 + j * v1 = x2 + j * v2

Rearranging for j:

j = (x2 - x1) / (v1 - v2)

Now, the particular value of j doesn't matter from the perspective of the question: you simply want it to be a whole number. For that to happen, the denominator has to divide the numerator.

In other words,

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

There are (at least) a couple of edge cases to watch out for:

• You also probably want (x2 - x1) / (v1 - v2) >= 0, otherwise the kangaroos would only be at the same place in the past.
• You should handle the case where v1 = v2 before applying the modulo operation - otherwise you'd get an ArithmeticException. There is a possibly valid solution in such a case, namely that x1 = x2.