CODEWITHSUNDEEP
algorithm
user3847425
user3847425

Reputation: 155

In tortoise and hare algorithm, Why we make the hare make 2 step forwards and check them

In tortoise and hare algorithm why do we always make hare go two steps forward and hare 1 step forward and then compare them, we can also make the hare go 1 step forward and then check if its equal again then increment both the tortoise and hare again check them if they are equal! I think this will help in finding the loop faster?

For eg. this pseudocode

tortoise := firstNode
hare := firstNode

forever:

  if hare == end 
    return 'No Loop Found'

  hare := hare.next

  if hare == end
    return 'No Loop Found'
   if hare==tortoise
return true

  hare = hare.next
  tortoise = tortoise.next

  if hare == tortoise
    return 'Loop Found'

Upvotes: 2

Views: 1425

Answers (1)

rici
rici

Reputation: 241701

The path consists of a tail and a loop; both the hare and the tortoise have to traverse the tail before they get to the loop. Since the hare moves two steps at a time, it gets to the loop first, and runs around the loop until the tortoise arrives. Up until the point at which the tortoise reaches the loop, it is not possible for the two of them to occupy the same cell.

Once the tortoise reaches the start of the loop, the hare is somewhere in the loop, effectively k steps behind the tortoise for some k, where k is certainly less than the loop size. For each step the tortoise makes, the hare makes two, which puts the hare one step closer to the tortoise. So after the tortoise moves one step, the distance between them is k-1 and then the next step it is k-2 and so on, until the hare catches up after k steps.

The hare never passes the tortoise in the loop, so there is no point checking for the hare being in the place the hare leaps over; it cannot be there. The extra check, therefore, will always fail, and including it will only slow the algorithm down.

Upvotes: 7

Related Questions