Как найти значения в огромном массиве?

Question

[cbgx74]

Вот такой вопрос мне задали на собеседовании, но я к сожалению не был к нему готов:

1) Есть большой массив значений представленных в бинарном виде
2) В этом массиве у каждого значение есть пара, такое же значение, и только у одного значения пары нет
3) Значения поступают в буфер, но буфер сильно меньше массива (скажем можно поместить только одно значение)
4) Найти значение без пары

Мне были даны подсказки:
- использовать бинарные операции
- след матрицы

Подскажите, куда хотя бы копать. Спасибо.

Answer 1

[tadex]

XOR через весь массив - на выходе будет одинокий элемент

Comments

[cbgx74]

Хм, я про это говорил. Видимо, что-то не пояснил.

[cbgx74]

При чет тут след матрицы? Можете пояснить?

[tadex]

При том же при чем интеграл по поверхности :)

[tadex]

сбить с ИСТИННОГО ПУТИ :)

[Станислав Клементьев]

интересно, собеседовал HR?

[Vlad161]

@cbgx74 @tadex а можете пояснить, что такое XOR и с чем его едят?

[cbgx74]

@Vlad161 Шутите? ru.wikipedia.org/wiki/%D0%A1%D0%BB%D0%BE%D0%B6%D0%...

Answer 2

[Дмитрий]

XOR - задачка тривиальная!!!
Задам другую:
Напишите рекурсивную функцию для вычисления факториала, которая будет вычислять результат итеративно.

Comments

[Noxa]

Поясните пожалуйста. Рекурсивное вычисление факториала понятно как сделать, а что значит "итеративное вычисление результата"?

[cbgx74]

Имеется ввиду через цикл, а не рекурсию. www.cyberforum.ru/cpp-beginners/thread322724.html

[Noxa]

То есть нужно написать рекурсивную функцию, которая циклом вычисляет факториал и потом вызывает сам себя для вывода результата. Какой смысл в такой формулировке задачи?

[cbgx74]

@Noxa Рекурсию можно заменить циклом