finddup.py

# 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)