CODEWITHSUNDEEP
c++algorithmfloyd-cycle-finding
WoooHaaaa
WoooHaaaa

Reputation: 20450

When will Floyd's cycle-finding algorithm fail?

I get an interview question about the Floyd's cycle-finding algorithm :

When will Floyd's cycle-finding algorithm fail ?

I mean, is there rule for finding the step between the fast and slow pointers ?

Upvotes: 2

Views: 1362

Answers (3)

Tanisha Roy
Tanisha Roy

Reputation: 1

okay, I'm solving this problem now and the same question occurred to me too.
The Floyd algorithm states that the fast pointer can be m times faster than the slow pointer. people generally take m as 2 i.e., fast advances by 2 steps while slow advances by only 1 step in every iteration. This particular value works for all structures and lengths of loop.
However, if we were to find the start of the cycle and we take m>2, then the algorithm fails in cases where there exists a loop of length m-1. In this case the cycle will be detected, but it fails on the part of finding the initial loop node.
This is something I've noticed but not sure how and why is it like that. Some insight will be helpful. thanks!

Upvotes: 0

NPE
NPE

Reputation: 500297

Under reasonable assumptions, it won't fail. It will either find a cycle or conclude that there isn't one.

The only failure scenarios I can think of are along the following lines:

  • there's a bug in the implementation;
  • the structure that's being traversed gets modified while the algorithm is in progress.

Upvotes: 2

Deepu
Deepu

Reputation: 7610

There may not be any possible failure situations for Floyd's cycle finding algorithm.

The only possible failure scenario occurs when it is computationally difficult to find the next node in a dynamically changing linked list.

Upvotes: 1

Related Questions