PY
py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#Recreation of a code I found on youtube
#Pick a random number,n, and create a list with a length of n+1. Fill the list with numbers 1 to n,in any order. There should be 1 duplicate number.
#example: [5,1,3,2,5,4,5]
def findduplicate(nums):
tortoise=nums[0]
hare=nums[0]
while True:
tortoise=nums[tortoise]
hare=nums[nums[hare]]
print("tortoise:",tortoise)
print("hare:",hare)
if tortoise==hare:
break
ptr1=nums[0]
ptr2=tortoise
while ptr1!=ptr2:
ptr1=nums[ptr1]
ptr2=nums[ptr2]
print("\nDuplicate:")
return ptr1
print(findduplicate([1,5,6,3,7,2,4,5]))
Enter to Rename, Shift+Enter to Preview
OUTPUT
Run