CODEWITHSUNDEEP
algorithmdata-structureslinked-listcycle-detection
Amarnath
Amarnath

Reputation: 8865

Cycle Detection Algorithm: Is there a condition for Tortoise and Hare to enter into cycle?

Recently I attended an interview and came accross the following question which I am not able to figure out.

Question-1:

As per the proof which I read Tortoise moves 1 step and Hare moves 2 steps at a time. I understood this and they will meet at some point since Hare moves twice the speed of Tortoise. Can't they have any random values like 2 and 3 or 3 and 5 or 2 and 4. If so, will they ever figure out the cycle? What is the condition for choosing the Tortoise and Hare values? Can we choose any random values?

Question-2:

Is there any condition for Tortoise and Hare to enter into the loop? Suppose if Tortoise and Hare have following values say 2 and 4 resp. And the linked list is like 

            3   
          /   \
    1 -  2     4
          \   /
            5

If Tortoise enters in to loop at node 3 and Hare enters loop at node 2 then they both never meet each other inside the loop. So is there a condition for Tortoise and Hare to enter the loop?

Are there any confined values that should be choosen such that they meet each other?

Upvotes: 3

Views: 694

Answers (3)

Shashwat Kumar
Shashwat Kumar

Reputation: 5287

Say tortoise start at point numbered T and take steps St and Hare start at H and take steps Sh.

The necessary and sufficient condition for them to meet is

|T - H| = k X gcd (St , Sh)

i.e. the difference in their starting position should be the multiple of gcd of their steps.

Upvotes: 2

Serge Rogatch
Serge Rogatch

Reputation: 15030

RE Q1: the greatest common divisor of tortoise and hare speeds must not be a divisor (other than 1) of loop length. So e.g. if gcd(vTortoise, vHare)=2, it will detect loops of odd lengths, but may fail for loops of even length. Q2 relates to the cases where it fails.

RE Q2: to detect a loop when the above restriction does not hold, i.e. when loop length is evenly divisible by M = gcd(vTortoise, vHare), loop will not be detected if tortoise and hare enter the loop at positions with different modulo M from the beginning of the loop. So in the above example, M=2 and loop will be detected if both hare and tortoise enter at positions with equal modulo M, e.g. 0 and 2, 0 and 4, 2 and 4, 1 and 3, etc. But loop will not be detected (thus tortoise and hare will travel infinitely) if they enter the loop e.g. at positions 0 and 1, or 0 and and 3, 1 and 2, etc.

Upvotes: 3

Sneftel
Sneftel

Reputation: 41474

The movement rates for the two must be relatively prime, in order to catch cycles of any length. I think that's a sufficient condition.

Upvotes: 1

Related Questions