Floyd’s Tortoise and Hare

Question

I recently found out about the Floyd’s Tortoise and Hare algorithm through YouTube. I understand how
the algorithm works

What I don’t really get is the way the guy in the YouTube video made the hare move twice as fast as the tortoise pointer
👇
tortoise=nums[tortoise]
hare=nums[nums[hare]]

Why does this code make the hare move twice as fast as the tortoise?

Recreation of the code. Also, this code is an application the algorithm to print out a duplicate number.

https://code.sololearn.com/cVAyvtsF08Z5/?ref=app

Answer 1

I just had an epiphany and figured it out.

If I have a list [1,5,6,3,7,2,4,5],
the tortoise goes: 5, 2, 6, 4, 7
the hare goes: 2, 4, 5, 6, 7

But since the hare goes num[nums[hare]], the hare actually goes:
5, 2, 6, 4, 7, 5, 2, 6, 4, 7
but the hare only stops at every other number, making it go twice as fast as the tortoise, which goes 5, 2, 4, 6, 7

Hope this helps anyone else wondering the same thing as me.

Answer 2

I don't know about hare but this seems to be a wrong algo!
Try to put big numbers in the list!

Answer 3

hi, i’m just commenting because i think this is very cool! i think to make the hare move twice as fast you could change the code to...

def findduplicate(nums):
t=0
tortoise=nums[t]
hare=nums[0]
while True:
tortoise=nums[t]
hare=nums[nums[hare]]
print("tortoise:",tortoise)
print("hare:",hare)
t=t+1
if tortoise==hare:
break

but it only works if the numbers are in order :(
i love this problem though! thank you for sharing!!!!

Answer 4

•—• • •-• ••• —- -• If the list contains 2,33,42,7,6,8,2
Then it would show an error 😐

Answer 5

Namit Jain
I think it says in the code, but this is an application of the algorithm I found on youtube.
The code only works if you enter numbers, 1 to n, in any order, into a list with a length of n+1. n is any natural number.

Answer 6

•—• • •-• ••• —- -• Ohk

Answer 7

My bad, forgot to say the requirements of the input for the code to work.