r_5_7.py

# -*- coding: utf-8 -*-
#!usr/bin/env python
# Excersise 5.7

"""
Let A be an array of size n ≥ 2 containing integers from 1 to n − 1, inclu- sive, with exactly one repeated. Describe a fast algorithm for finding the integer in A that is repeated.
"""

import random


def sample(n=2):
    """Produces one sample for testing."""
    assert n >= 2
    l = []
    for i in range(1, n):
        l.append(i)
    l.append(random.choice(l))
    random.shuffle(l)
    return l

def find(l):
    """
    Let A be an array of size n ≥ 2 containing integers from 1 to n − 1,
    inclusive, with exactly one repeated. Describe a fast algorithm for
    finding the integer in A that is repeated.
    
    len(l) = 10
    timeit 100000 loops, best of 3: 14.2 us per loop
    len(l) = 1000
    10000 loops, best of 3: 95.1 us per loop
    """
    l.sort() # O(nlogn), guarranteed
    last = None
    for i in l: # O(n)
        if i == last:
            return last
        last = i

def find2(l):
    """
    
    len(l) = 10
    timeit 100000 loops, best of 3: 12.9 us per loop
    len(l) = 1000
    100000 loops, best of 3: 10.4 us per loop
    """
    n = len(l) # O(1)
    return sum(l) - (n*n - n) / 2 # O(n) for sum()