Две простые задачки.
1. Имеем массив А, состоящий из N чисел, и массив В, образованный из А добавлением одного числа (кол-во элементов N+1). Массивы неотсортированы, массив В перемешан после добавления числа. Задача: найти добавленное число за линейное время.
Пример:
A = {5, 46, 5, 34, 2}
B = {34, 46, 5, 3, 2, 5}
x = 3
Очевидное решение, не правда ли? Также можно легко свести его к задачке про поиск непарного
2. Добавляем не один, а два элемента. Опять-таки, найти их за линейное время.