Assuming there is a hare and a tortoise at the beginning and the hare moves 2 steps at one time while the tortoise moves 1 step. If there is a cycle in the sequence, they both will meet finally at some point. Or if there’s no such a cycle, they will both reach the end.
Where does the cycle start from?
Initially, the hare and tortoise are at the start of the sequence. The hare moves 2 steps at a time while the tortoise moves 1 step. Assuming they meet after k iterations, the length of the non-cyclic part is x, circumference of the cycle is p, and the distance between the beginning of the cycle to the place they meet is y, we have:
k = x + a * p + y. a is a non-negative integer representing the number of loops that tortoise traveled, and k is the distance that the tortoise moved.
2 * k = x + b * p + y. b is another non-negative integer representing the number of loops that hare traveled, and 2 * k is the distance that the hare moved.
On solving the above two equations, we get: k = (b — a) * p
Now we put the hare back to the beginning and both hare and tortoise move 1 step at a time.
The place where they meet is the start of the cycle. This is because when the hare travelled another x, the tortoise is at the k + x = (b — a) * p + x.
The final step says: k = (b-a)*p. Can anyone please explain how does this ensure that after traveling additional x distance, the tortoise would be at the starting point ?
1
When you restart the hare at 0, the tortoise is at k=(b-a)p.
After you move them both x steps, the hare is at x and the tortoise is at (b-a)p + x. They will meet there, because it’s the first time that they’re both in the cycle, and the difference is divisible by p.