Найти недостающие и повторяющиеся элементы в массив в линейном времени и постоянном пространстве

Вам дан массив из N 64-битных целых чисел. N может быть очень большим. Вы знаете, что каждое целое число 1..N появляется в массиве один раз, за ​​исключением того, что одно целое число отсутствует и одно целое число дублируется.

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

Источник: http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/