HackerRank: Kangaroo Jump

Answer and thoughts

My first approach to solving this problem was to consider independently the start position and jump distance of each kangaroo so the thought was that: if the first kangaroo has the higher position then the second kangaroo must have the higher jump distance so I wrote this code:

if x1 > x2 and v1 < v2
 return "YES";
elif x2 > x1 and v2 < v1 
 return "YES";
else 
  return "NO";

However, this solution passed only 12 test cases out of the 30 test cases.

The next thought I had was to determine if there could be a relationship between each jump that the kangaroos make… I sat with this for a while then finally opted for checking out the discussions and in doing that I found an equation that states the relationship as:

x1 + n*v1 = x2 + n*v2

Where n is the number of jumps that would make both kangaroos be in the same position at the same time. Using the rules of linear algebra I found that the value of n would be:

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

This is simply the value of n which must always be positive and non-zero. The required condition to fulfill this is:

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

To avoid a division by zero, I included a condition that returns no if both kangaroos have the same jump distance, giving the solution:

if v1 == v2  
   return "NO";
else
   return n == 0 ? "YES" : "NO";

Using this solution still caused a failure in some of the test cases and lucky for me one was not locked (test case 1) and while debugging I discovered that the initial conditions had to be included i.e. if the first kangaroo has a greater jump distance than the second kangaroo then it must also have a lower start position.

int n = (x1 - x2) % (v2 - v1);
if x1 > x2 and v1 > v2  
   return "N0";
elif x2 > x1 and v2 > v1
   return "NO";
elif v1 == v2 
   return "NO";
else
  return n == 0 ? "YES" : "NO";

aaaaand Viola! We still have a failed test case, yes, test case 10 is still incorrect and it's hidden! Well at this point I just had to open it up costing me five hackos :(

Input:  43 2 70 2

I tried to see what could be wrong I had already taken care of the condition that V1 and V2 might be equal so I wondered...well here’s a funny story as with most debugging process, I spent quite a while trying to figure out what was wrong until I finally noticed that the error was a runtime error, not a wrong answer error (this took 45mins).

From my solution, I had calculated the value of n before checking the condition for v1 and v2 equality so I had to modify the code, and put the conditions before calculating anything, a valuable lesson I must say.

if x1 > x2 and v1 > v2  
   return "NO";
elif x2 > x1 and v2 > v1
   return "NO";
elif v1 == v2 
   return "NO";
else
   return (x1 - x2) % (v2 - v1) == 0 ? "YES" : "NO";

So I spent a total of 2 hours solving this problem. Yes, who would have thought, but glad I reached the end. The most important (asides from the cognitive) lesson I learned from this process was read everything carefully and determine exactly what is wrong before trying to find a solution.