Задача головоломка 1

Когда учил вышку в универе часто ловил себя на мысли, что не хватает интересных задачек, тех что были в школе, решая которые приходилось думать головой, а не следовать шагам какого-то сложного алгоритма, в конце получив правильный ответ.

Так же сейчас не хватает интересных задачек по программированию, например как были по ассемблеру, когда учился у Олега Романовского.

Решил не пропускать интересные задачки и решать их в свободное время.

И так первая задача звучит так (услышал от Тумара Максима):
Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
число в этом массиве повторяется два раза. Найти это число за время O(N).

Решение ниже.






тут мы думаем ...




O(N) - это грубо говоря один проход по массиву, один for.
Сначала я пытался как-то хитро сортировать массив, смотреть на него как на дерево, но O(N) никак не получалось (за O(N) я принимал даже (O(a*N)+b) где a,b - константы), но потом понял, что использую не все данные.
Есть же ещё ограничение на элементы - максимальный M.

Идея решения:
создать массив длинной в M и инициализировать его например 0. Далее проходя по исходному массиву переписываем каждый элемент на своё место - массивДлинйМ[i]=i. Перед записью проверяя если на месте i в массиве уже 0, то значит элемент встретился 1 раз, если уже i то мы нашли дубликат.

Код на python:


import random




if __name__ == "__main__":
    N = 10       #range of array
    M = 100      #max possible value of element in array


    #array of N-1 elements
    arr_with_no_dup = random.sample(range(M), N-1)
    #array with range of max element value
    arr_of_all_elems = [x*0 for x in range(M)] 
    #position of element wich will be duplicated        
    elem_to_be_dup = random.sample(range(N-1), 1)[0]  
    #position of the duplicate 
    dup_pos = random.sample(range(N), 1)[0]            
    arr_with_dup = []


    #make array with duplicated element
    arr_with_dup = arr_with_no_dup[0:dup_pos] + [arr_with_no_dup[elem_to_be_dup]] + arr_with_no_dup[dup_pos:]
    print arr_with_no_dup
    print arr_with_dup


    for i in arr_with_dup:
        if arr_of_all_elems[i] != i:
            arr_of_all_elems[i] = i
        else:
            print "duplicated element is ", i
            break



результат выполнения:

[95, 91, 14, 23, 59, 10, 46, 34, 18]
[95, 46, 91, 14, 23, 59, 10, 46, 34, 18]
duplicate is  46

вот и всё. может есть ещё решения - предлагайте.
На решение ушла 1 пара :)