CareerCup

Here's my attempt. If there's a loop, then we know eventually both pointers would have fallen into the loop. Assume the loop consists of N nodes. Let the current position of the fast-moving pointer (the one that moves 2 steps) be 0, and let that of the slow-moving pointer (the one that moves 1 step) be P. In other words, consider the slow-moving pointer as P nodes ahead of the fast-moving one.

After "t" iterations, the positions of the fast & slow pointers will be:
(2t) % N
(P + t) % N

Note that both values would be the same when t is P, so by having a fast and slow moving pointers we are guaranteed they would eventually meet.

My first question - are such questions asked to college freshers or even to experienced candidates with professional background?

I am not sure what do you mean by 'induction hypothesis' and how can you use induction.

How we detect loop is


Let's say that there're two pointers r (for rabbit) and t (for tortoise).

while(1)
{
	r = r+2;
	t = t+1
	if( r == t )
		loop found
}

In other words if rabbit and tortoise are running in a straight line, tortoise would never be able to catch rabbit before it reaches the end of race unless rabbit sleeps. But since rabbit ran and found that tortoise is at same point as himself, rabbit must have run in circle.

Now rabbit is always running in a step of 2, so its values will always be like

0 - 2 - 4 - 6 - 8.......
Tortoise is crawling with step of 1, so its value will always be like
0 - 1 - 2 - 3 - 4....

For rabbit to meet tortoise, rabbit should be one step behind tortoise (because when tortoise will crawl by one, rabbit will hop by two steps jumping over tortoise's previous position and meet it).

For that to happen tortoise should be at some position in cycle so that (tortoise's position + 1) and (rabbit's position + 2) meets at the same 'even position'.

x+1 = y+2
1. if both x and y are even then x+1 will be odd, and y+2 will be even, equality won't hold
2. if both x and y are odd then x+1 will be even and y+2 will be odd, equality wont hold
3. if x is even and y is odd then x+1 will odd and y + 2 will also be odd
4. if x is odd and y is even, then x+1 will be even and y+2 will also be even.

x can be both even and odd.
y can be even if loop is of even size (because it will just keep hopping on all nodes numbered divisible by 2 and x will take each odd position so condition 3 can be true for an odd number x but even y such that
x+1 = y+2

y can be take both even or odd for loop of odd size , since x will take value every odd node and y will take value every odd node as well, both will meet when x+1 = y+2

Assume the loop has 'n' nodes.
Let the node in the loop that runner first lands at be 'N'.
After 'i' iterations, runner would be 2*i % n nodes away from N.

Assume the follower arrived at N, 'k' iterations behind the runner.
After 'i' iterations (we are interested only in i >= k), follower would be (i - k) % n nodes away from N.

The question is now reduced to proving that for any 'k' there exists an integer 'i' such that,
2*i % n = (i - k) % n
=> 2i = i - k + cn (where c is any integer)
=> i + k = cn

Since we are interested in only non-negative 'k' and i > k,
i = cn - k, where c is any integer > k/n

Let x be the number of iterations. 2x for double case.
P be the pth node you are visiting.

Let s be the number of nodes in a linked list that are singled.
Let c be the number of nodes in a linked list that are cyclic. As in going to c+1th node will put you at position c+1 again.

So we are proving equation:

s + ( x -s ) % c = s + ( 2* x - s ) % c
s and c can be any constant.
x is variable.
( x - s) % c = (2 * x - s ) % c
let x = c
( c - s ) % c = ( 2 * c - s ) % c
if c > s then this will be true as you will get c -s = c - s
if s > c then we can still prove this just let x = some multiple * c which is greater than s.

Here is another mathematical proof.

Imagine two positions are in loop separated by 'z' distance within the loop, where `z < n` where 'n' is number of elements in loop.

We can say that, after 'm' iteration, two positions will be:

m%n
(2*m+z)%n

Now, we need to prove that for any 'z' and 'n', there is always a 'm' which can make above two equations equal. Lets find that m:

m%n = (2m+z)%n
opening mod

|2m+z - m| = cn where c E [0, inifnity)
|m+z| = cn

since z < n
m= n - z

So two positions separated by 'z' distance within a loop, will always meet if one proceed 2* of other after n-z iteration.

you can think like this.
the faster step is x. and the slower is y. when the come into the loop. their distance is d(y ahead x, it's a circle).
so if we want they meet, we should make this formula stands.
(a(x-y))%n = d
am%n = d
0 < d < n; a is a variable.
so how can it always stands?
m and n is must be relatively prime.
1 will be always relatively-prime with any positive number. so (x=2,y=1) would be a not bad choice

Suppose the link has a loop with length N. Suppose that when the follower enters the loop, the runner needs to walk distance k to catch the follower (or the following is N-k distance after the runner.

If k = 0, the runner and the follower meet. We have a loop.

Otherwise, in each step, the runner moves 2 steps, while the follower moves one step, the distance between the runner and the follower decreases by 1.

After k steps, the runner can eventually catch the follower.

This needs proof?