Нахождение потерянного элемента массива

Опубликовано Jun 6, 2013 в Манипуляция битами, Массивы и строки | 26 коммент.

, ,

Нахождение потерянного элемента массива

Имеется набор из N различных целых чисел. Из него нужно создать одномерный массив, содержащий 2*N элементов, помещая в массив каждое число из исходного набора ровно по два раза. После этого элементы массива переставляются случайным образом. Известно, что в результате этих действий РОВНО ОДИН из элементов массива потерялся, а массив оказался размерности 2*N -1. Как это выглядит можно посмотреть на рисунке.

Нужно найти испорченное значение в массиве, то есть результатами для трех приведенных вариантов повреждения данных должны быть числа 4, 4 и 5 соответственно. Желательно придумать алгоритм, который не переставляет элементы исходного массива, не портит его, не выделяет памяти под дополнительный массив и работает за один проход по исходному массиву.

 


Автор публикации: