задачка (программистское)

Задачка для программистов и интересующихся. Наверняка известная, но мне в такой форме не встречалась, и понравилась.

Дан массив размером N, в нем есть только числа от 1 до N-1 (необязательно все, необязательно по порядку). Очевидно, какие-то из них повторяются. Найти какое-то число, которое встречается в массиве больше одного раза.

Суть в том, чтобы сделать это с как можно лучшей сложностью времени и места. Скажем, тривиально сделать это за O(N) времени с O(N) места. Можно лучше. Исходный массив не бесплатный: его можно менять, но это считается в бюджет места.

Update: все скрытые комментарии с правильными решениями раскрываются. Не заглядывайте в комментарии, если хотите дальше думать сами - там есть много правильных решений. Оптимальное решение этой проблемы выполняет задачу за O(N) времени, O(1) места.

сообщение

Горное озеро с поэтичным названием "Слеза Облаков", Lake Tear of the Clouds, находится на горе Марси в штате Нью-Йорк. Википедия рассказывает, что в 1901-м году еще вице-президент Теодор Рузвельт находился возле этого озера, когда получил сообщение, что состояние президента Маккинли, которого за две недели до того ранил анархист, сильно ухудшилось. Рузвельт спустился по склону горы к ближайшей станции дилижансов, оттуда поехал на дилижансе к железнодорожной станции, а оттуда на поезде прямо в президенты.

Так вот, когда вы прочитали, что Рузвельт, гуляя около этого озера, "получил сообщение", то какая картинка у вас в голове появилась? Да? Верно ведь? - и у меня такая же.

об отличной кинокритике

Неизвестный мне кинокритик Matt Zoller Seitz составил подборку лучших сцен из фильмов 2010-го (все по-англ.). Меня очень впечатлил формат его комментариев: бегущие параллельно ролику из фильма титры, объясняющие что критику нравится в этой сцене, что режиссер делает необычного, как это откладывается у зрителя.

Такую вот кинокритику я бы еще смотрел и смотрел. Очень впечатлило.

Вот, например, первый из роликов, про сцену из "вампирского" фильма, который я и не видел вовсе. Но там еще много хороших - и про "Toy Story 3", например, и про сцену гребли из "The Social Network", и еще.