I’d like to share with you a simple problem. Simple in a way that it can be solved using brute force and algebra with time complexity of O(n).
Difficult in a way that with a little help of algebra, the time complexity can go down to O(1).
When questions like this shows up in an interview, brute force is a way to solve it. Yet, not the most efficient way.
Two rabbits A and B are heading toward the same destination from two different starting points.
Rabbit A starts at location x1 with velocity of v1 meters per jump.
Rabbit B starts at location x2 with velocity of v2 meters per jump.
Given x1, x2, v1, v2, can you figure out if two rabbits would bump into each other at the same time?
If I write out the story in math, then it becomes clear that we are trying to solve the problem if two lines would ever intersect.
For example, Rabbit A is at 1 with velocity of 3 meters per jump and Rabbit B is at 4 with velocity of 1 meters per jump.
We get:
1+3k = y1
4+k = y2 where k is number of jumps and y is the final location after k jumps
Now, we want to know whether y1= y2 at some k.
Intuitively, I would write a loop for k and only breaks out from the loop when y1= y2. This approach gives us O(n) in terms of time complexity.
Can you think of a way to reduce the time complexity to O(1)?
Hint: for loop is not indispensable!