Determining if the kangaroos will land in the same position

Question

Problem

There are two kangaroos on an x-axis 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?

My Solution

#include <iostream>
using namespace std;

int main(){
    int x1, v1, x2, v2;
    cin >> x1 >> v1 >> x2 >> v2;

    // If one kangaroo is behind the other AND moving slower, 
    //    he/she will never catch up to the other one
    if ((x1 < x2) && (v1 < v2)) cout << "NO";
    else if ((x2 < x1) && (v2 < v1)) cout << "NO";

    // Otherwise, move each kangaroo one jump at a time until 
    //     the one behind is no longer behind. 
    else {
        if (x1 < x2) {
            while (x1 < x2) {
                x1 += v1;
                x2 += v2;
            }
        } else {
            while (x2 < x1) {
                x1 += v1;
                x2 += v2;
            }
        }

        // Once he/she is no longer behind the other, check to see
        //    if he/she is in the same position, or if he/she has passed
        if (x1 == x2) cout << "YES";
        else cout << "NO";
    }
    return 0;
}

I am wondering if there is a way to optimize my code for this particular HackerRank problem. I have gotten all of the correct answers, and none of them timeout so for the problem it's 'good enough,' but I am curious if there is a better way of doing it.

Do I use too many conditionals, loops, etc? I have a bad habit of "do everything in for loops, if statements, etc."

Answer 1

Closed form solution

A better approach is to calculate the intercept point directly and then check whether or not it is an integer. The time of intercept is:

$$t = \frac{x_2 - x_1}{v_1 - v_2}$$

where both numerator and denominator are integers, but their ratio may not. We can also handle all special cases from the ratio.

bool kangaroos_meet(int x1, int v1, int x2, int v2) {
    int numerator = x2 - x1;
    int denominator = v1 - v2;
    if (denominator == 0)                // same velocity
    {
        return numerator == 0;           // they meet always or never
    }
    if (numerator % denominator != 0)    // intercept point not an integer
    {
        return false;
    }
    int t = numerator / denominator;     // calculate intercept point
    return t >= 0;                       // intercept point lies in the past
}

Answer 2

Put business logic in functions

The first thing that I would do is create a function. Then main becomes

int main(){
    int x1, v1, x2, v2;
    std::cin >> x1 >> v1 >> x2 >> v2;

    if (kangaroos_meet(x1, v1, x2, v2)) {
        std::cout << "YES";
    } else {
        std::cout << "NO";
    }
}

Now we only write each output option once. You could use the ternary operator to reduce this to just one cout, but I find this form more readable.

Also, main only does input and output. The "problem" is entirely handled in the kangaroos_meet function.

I removed using namespace std;, as it uses more characters than just writing std:: three times. Which I find more readable anyway.

I removed return 0; as modern compilers will insert it for you.

Bug

In your original code, you will loop forever if the kangaroos have different starting points but the same velocity.

Simplify logic

You have separate logic depending on which kangaroo is further ahead. You can simplify this with a recursive call.

bool kangaroos_meet(int x1, int v1, int x2, int v2) {
    if (x1 < x2) {
        // if the second kangaroo is ahead of the first
        // switch so that the one ahead is first
        return kangaroos_meet(x2, v2, x1, v1);
    }

    if (x1 == x2) {
        // if already at the same location, true
        return true;
    }

    // x1 > x2 because it's not less than or equal
    if (v1 >= v2) {
        // If the first kangaroo is ahead and as fast or faster
        // then the second kangaroo will never catch up
        return false;
    }

    do {
        x1 += v1;
        x2 += v2;
    } while (x1 > x2);

    return x1 == x2;
}

By calling the function recursively, we save having two sets of logic. Now we just have one set of logic that handles the case where the first kangaroo is ahead of or tied with the second. If that's not the case, we simply switch the two kangaroos.

This fixes the problem of equal speed kangaroos, but now we need to check that the kangaroos aren't already at the same location. And we need to check that before we compare velocities, as we removed the check that the first kangaroo is ahead of the second.

Adding "or equal to" to the velocity comparison handles same speed kangaroos correctly.

The while loop is essentially the same, although we can make it a do/while. We already know that x1 > x2 for the first iteration. We don't have to check.

Then we check to see if they met or if the second one passed the first. This is the same check as in your original code.

Answer 3

Naming

Yes, I know that the assignment gives single letter variables, but that's the way of the mathematician, not the way of the programmer. A programmer needs to be able to see in an instant what a variable or method is referring to.

In this case, I would use the variable names firstPosition, secondPosition, firstSpeed and secondSpeed.

Answer 4

Namespaces

using namespace std; is considered bad practice. Short code is not a requirement in C++, clear code is preferred. It's a thing commonly taught to new C++ programmers because it's 'easier', but it will royally bite you in the behind when conflicts arise.

Return

return 0; is a legacy from (pre-C99) C. In C++, it's no longer required to write this manually at the end of main. The compiler will take care of returning 'normal' if no errors were thrown or other returns (like -1) are encountered.

Answer 5

I have just analyzed your code and here are my analysis-

It's always good to check the boundary condition (x2>x1)or not? but if you read the constraint given in the problem statement it's clearly defined that x2 will be always greater than x1.

I can see you have used two while loops in your code but you can avoid this by using some mathematics.

If you just analyze closely you can see come up with a formula to solve this question directly which would be faster.

Here is the explanation to derive the formula from the problem statement.

As mentioned in the question both kangaroo will meet at the same location at the same time. So the distance covered by kangaroo 1 should be equal to the distance covered by kangaroo 2 which can be calculated as

x1+v1*j=x2+v2*j (using distance =velocity *time (here time is nothing just a jump so using j)).

Now solve for j.

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

As both kangaroos should meet at the same time, the number of the jump should be the same by both of the kangaroo to achieve this. And we know jump will always be an integer value. It can never be a float like 1.2 jumps something like that.

So we have to make sure jump must be an integer value or we can say when we divide (x1-x2) by (v2-v1) it should give the quotient which is an integer value (which is possible only when the remainder is zero).

So calculating

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

using the modulo operator instead of division and checking whether it's zero or not.

If it's zero, it means there is some integer number of jumps exist which will bring both kangaroos at the same location at the same time.

But you have to make sure v1 which is the velocity of kangaroo 1 must be greater than v2 otherwise kangaroo 1 will never be able to catch kangaroo 2. So this is the prerequisite.

Here is the solution -

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";

    }

and the detail video explanation can be found here.

Answer 6

x1: initial location of kangaroo 1 & x2: initial location of kangaroo 2

If it is given that x2 > x1

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

    int i;
    for(i=0; x1<x2; i++){
        x1 = x1 + v1;
        x2 = x2 + v2;
        if(x1 == x2){
            return "YES";
        } 
    }   
    return "NO";
}

Below solution covers all the possibilities like, x1 > x2 or x1 == x2 or x1 < x2.

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

    int i, flag = 0;

    if(x1 > x2){
        for(i=0; x1>x2; i++){
            x1 = x1 + v1;
            x2 = x2 + v2;
            if(x1 == x2){
                return "YES";
            }
        }
    }else if(x1 < x2){
        for(i=0; x1<x2; i++){
            x1 = x1 + v1;
            x2 = x2 + v2;
            if(x1 == x2){
                return "YES";
            } 
        }   
    }else
        return "YES";

    return "NO";
}