Number Line Jumps HackerRank Algorithms Question

Question

I am looking at the HackerRank problem Number Line Jumps:

You are choreographing a circus show with various animals. For one act, you are given two kangaroos on a number line ready to jump in the positive direction (i.e, toward positive infinity).

• The first kangaroo starts at location 𝑥1 and moves at a rate of 𝑣1 meters per jump.
• The second kangaroo starts at location 𝑥2 and moves at a rate of 𝑣2 meters per jump.

You have to figure out a way to get both kangaroos at the same location at the same time as part of the show. If it is possible, return YES, otherwise return NO.

Example

𝑥1 = 2
𝑣1 = 1
𝑥2 = 1
𝑣2 = 2

After one jump, they are both at 𝑥 = 3, (𝑥1 + 𝑣1 = 2 + 1, 𝑥2 + 𝑣2 = 1 + 2), so the answer is YES.

Constraints

0 ≤ 𝑥1 < 𝑥2 ≤ 10000
1 ≤ 𝑣1 ≤ 10000
1 ≤ 𝑣2 ≤ 10000

The algorithm I wrote doesn't pass all the tests case on HackerRank, I can't see where I'm doing wrong?

function kangaroo(x1, v1, x2, v2) {
    let   firstKangaroo = x1 + v1;
    let   secondKangaroo= x2 + v2;
    let   trueFalse = false; 
    let   maxLimit =  10000;
    let i = 0;
    for(;i <= maxLimit;i++) {
        if(firstKangaroo==secondKangaroo){
            trueFalse = true;
            break;
        }
    }
     return trueFalse ? "YES" : "NO";
}

I threw it into the v1 variable with x1. I did the same for x2 and v2. I made the loop continue until 10000. If x1 + v1 = x2 + v2 then it should return true, not false. My code is running without errors, but it can't pass all the tests cases on HackerRank. I can't find where I went wrong.

Answer 1

Several issues:

• In your loop nothing is happening with firstKangaroo nor secondKangaroo (they don't jump), so if in the first iteration they are not equal, they will still be unequal in the second, third, ... and all other iterations of the loop. So the loop serves no purpose.
• 10000 tries might not be enough to spot the jump where both kangaroos meet.

Moreover, this idea is not efficient. Look at the mathematics of this problem:

If the kangaroos meet, then there must be a number of jumps k such that:

x1 + k*v1 == x2 + k*v2

So then

(x1 - x2) == k*(v2 - v1) 

...and that k must be an unsigned integer, i.e. we should check that (x1 - x2) is a multiple of (v2 - v1). Also their signs should be the same, and then the remainder after division should be 0 -- we can use the % operator for that.

So:

function kangaroo(x1, v1, x2, v2) {
    return Math.sign(x1 - x2) === Math.sign(v2 - v1) && 
          ( v1 === v2 || (x1 - x2) % Math.abs(v2 - v1) === 0) ? "YES" : "NO";
}

// Test run:
console.log(kangaroo(0, 2, 5, 3));

As in the code challenge it is given that x1 < x2 we can simplify a bit:

function kangaroo(x1, v1, x2, v2) {
    return v2 < v1 && (x2 - x1) % (v1 - v2) === 0 ? "YES" : "NO";
}

// Test run:
console.log(kangaroo(0, 2, 5, 3));

Answer 2

One approach, different from trincot's mathematical analysis is to test until the faster-moving kangaroo is ahead of the slower one, stopping if they meet. If they haven't by then, they never will. We can do this with a simple enough recursion:

const kangaroo = (x1, v1, x2, v2) => 
  v1 < v2
    ? kangaroo (x2, v2, x1, v1)
  : x1 == x2
    ? 'YES'
  : v1 == v2
    ? 'NO'
  :  x1 > x2
    ? 'NO'
  : kangaroo (x1 + v1, v1, x2 + v2, v2)


console .log (kangaroo (0, 3, 4, 2))
console .log (kangaroo (0, 2, 5, 3))

If the faster one is second, we swap them. If they're already in the same spot, we're done. If not, and they have the same-size jump, they can never meet. If the faster one is ahead of the slower one, then they won't ever meet. Otherwise, we make a jump (by incrementing x1 by v1 and x2 by v2) and test again.