0

Floyd’s Tortoise and Hare

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

26th Aug 2020, 2:04 AM
•—• • •-• ••• —- -•
•—• • •-• ••• —- -• - avatar
7 Respostas
+ 2
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.
27th Aug 2020, 8:07 PM
•—• • •-• ••• —- -•
•—• • •-• ••• —- -• - avatar
+ 1
I don't know about hare but this seems to be a wrong algo! Try to put big numbers in the list!
26th Aug 2020, 3:56 AM
Namit Jain
Namit Jain - avatar
+ 1
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!!!!
27th Aug 2020, 12:23 PM
madeline
madeline - avatar
+ 1
•—• • •-• ••• —- -• If the list contains 2,33,42,7,6,8,2 Then it would show an error 😐
27th Aug 2020, 8:12 PM
Namit Jain
Namit Jain - avatar
+ 1
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.
27th Aug 2020, 10:01 PM
•—• • •-• ••• —- -•
•—• • •-• ••• —- -• - avatar
28th Aug 2020, 3:25 AM
Namit Jain
Namit Jain - avatar
0
My bad, forgot to say the requirements of the input for the code to work.
26th Aug 2020, 4:34 AM
•—• • •-• ••• —- -•
•—• • •-• ••• —- -• - avatar