patterncppMajor
Determining if the kangaroos will land in the same position
Viewed 0 times
samedeterminingthekangaroospositionlandwill
Problem
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
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
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
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."Solution
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.
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
}Code Snippets
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
}Context
StackExchange Code Review Q#139896, answer score: 33
Revisions (0)
No revisions yet.