about summary refs log blame commit diff
path: root/scratch/facebook/find-unique-int-among-duplicates.py
blob: 56032aa05c8cbb9bb7d47a5a20cfc20c71f0a353 (plain) (tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
















                                         
import random

def find_duplicate(xs):
    mini, maxi, acc = xs[0], xs[0], xs[0]
    for i in range(1, len(xs)):
        mini = min(mini, xs[i])
        maxi = max(maxi, xs[i])
        acc = acc ^ xs[i]
    mask = mini
    for i in range(mini + 1, maxi + 1):
        mask = mask ^ i
    return mask ^ acc

xs = [5, 3, 4, 1, 5, 2]
print(xs)
result = find_duplicate(xs)
print(result)