HackerRank: Kangaroo

Everybody loves a kangaroo right? Except maybe if you are Australian! Anyway in this post we shall talk both about snakes and mammals, or more specific Python and Kangaroos. I have started on learning a bit of Python and using HackerRank to learn my ways around. I have been solving a few puzzles by now.  The ones I have solved so far, are no where near the complexity of Project Euler. Apart from the fact that quite a few of the project euler problems are actually represented at HackerRank, but with more test cases, so you have to write the code a little more generically. But more about that later, because I will likely solve a few of the Project Euler problems in Python while learning it.

Anyway, the first problem I solved, which might be worth spending a minute or two about, is the problem called Kangaroo.

The short description of the problem is as follows

There are two kangaroos on a number line ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location x1 and moves at a rate of v1 meters per jump. The second kangaroo starts at location x2 and moves at a rate of v2 meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they’ll ever land at the same location at the same time?

Input Format
A single line of four space-separated integers denoting the respective values of x1, v1, x2 and v2

Note: The two kangaroos must land at the same location after making the same number of jumps.

Simple algebraic solution for Kangaroo

Of course we could make a loop that terminates once the fastest kangaroo is in front. That would definitely work for us. However, we don’t need loops. Since we know that they must make the same number of jumps j. We can solve the equation

This can be rewritten as

If that have a positive solution integer solution then the kangaroos will meet. However, there is one special case we need to check as well. If the kangaroos have the same speed,  then the divisor will end up zero, and then we will get an error. However, if they have the same speed, they only meet if they also have the same start location. So that is pretty easy to check for.

#!/bin/python3

import sys

def kangaroo(x1, v1, x2, v2):
    
    #The case of same speed
    if v1 == v2 and x1 == x2:
        return 'YES'
    elif v1 == v2:
        return 'NO'
    
    x = (x2-x1) / (v1-v2)    
    if (x == round(x) and x > 0):
        return 'YES'
    else:
        return 'NO'
    
    
x1, v1, x2, v2 = input().strip().split(' ')
x1, v1, x2, v2 = [int(x1), int(v1), int(x2), int(v2)]
result = kangaroo(x1, v1, x2, v2)
print(result)

This passes all the test cases for me. To be quite honest I have yet to figure out how to actually time and thereby compare different solutions. But I guess I will find out eventually.

Posted by Kristian

5 comments

Martin Tirtawisata

Hey Kristian,

Thanks for the post. It was really helpful.

Though I’m still curious about the rounding up of x.

I tried removing (x === Math.round(x)) in the if statement in HackerRank and some test failed.

So why do we have to round it?

Thanks very much for answering if you have the time.

What does this ‘j’ mean? And can you please explain the meaning behind this equation

I would like to know , as to what it means when the answer of j is positive or negative. How do you relate that if the value of j is positive, they will meet, and that if j is negative they wont meet? Sorry if that question is stupid

Hi @GoSan, no thing such as a stupid question, The value of j is number of jumps the kangaroos will do if they meet! or in other words the value which when multiplied by the slower kangas speed and faster kangas speed(who was behind), will make them meet, the initial distance is x1-x2 and the relative velocity between them is v1-v2, so in physics term, it is the time to meet, think in whatever way you like.

Aviv Murlakov

@Martin Tirtawisata
We have to check the the number of jumps is not only positive but an integer, since a kangaroo cannot make 52 and 2/3 of a jump for example, only 52 or 53.

Leave a Reply