blob: 7c491aef604e71839591dfde3888e4a1412c02e7 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import random
def find_duplicate(xs):
print(xs)
# entry point in our cycle is the duplicate
i = xs[0]
j = xs[xs[0]]
while i != j:
print(i, xs[i], j, xs[j])
i = xs[i]
j = xs[xs[j]]
# detect cycle
j = 0
while i != j:
i = xs[i]
j = xs[j]
return xs[i]
n = random.randint(5, 10)
xs = [random.randint(0, n - 1) for _ in range(n)]
result = find_duplicate(xs)
print(xs, result)
|
