Skip to content

Instantly share code, notes, and snippets.

@theicfire theicfire/finddup.py
Last active Aug 29, 2015

Embed
What would you like to do?
# Q: Given a list of length n+1 with numbers from 1 to n, there will be at least one duplicate. Find it.
# Running time: O(n). Space: O(1). Or rigorously O(lgn) given that a constant variable to represent the number "n" grows with lgn.
# http://stackoverflow.com/questions/6420467/find-any-one-of-multiple-possible-repeated-integers-in-a-list/6420503#6420503
import random
import pytest
def find_dup(lst):
assert(len(lst) >= 2)
assert(all(map(lambda x: 0 < x < len(lst), lst)))
#find cycle
slow = lst[len(lst)-1]
fast = lst[len(lst)-1]
while True:
slow = lst[slow - 1]
fast = lst[fast - 1]
fast = lst[fast - 1]
if slow == fast:
break
#restart fast and step by 1
fast = lst[len(lst)-1]
while fast != slow:
fast = lst[fast - 1]
slow = lst[slow - 1]
return slow
def find_dup_slow(l):
a = {}
for i in range(len(l)):
if l[i] in a:
return l[i]
a[l[i]] = True
return None
def test_first():
a = [1, 3, 2, 4, 3]
assert find_dup(a) == 3
assert find_dup_slow(a) == 3
def test_first2():
a = [1, 3, 2, 4, 5, 1]
assert find_dup(a) == 1
def test_first3():
a = [1, 2, 2, 4, 5, 3]
assert find_dup(a) == 2
def test_first4():
a = [1, 2, 4, 4, 5, 3]
assert find_dup(a) == 4
def test_first5():
a = [4, 2, 4, 4, 5, 3]
assert find_dup(a) == 4
def test_noloop():
a = [1, 2, 3]
with pytest.raises(AssertionError):
find_dup(a)
def test_more():
for i in range(200):
length = int(random.random() * 100) + 2 # Has to be at least length 2
l = range(1, length)
l.append(int(random.random() * (length - 1)) + 1)
random.shuffle(l)
assert find_dup(l) == find_dup_slow(l)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.