Повторюсь, что какое-то решение задачи написать можно довольно легко. Банальный вариант - вложенный цикл, для каждого элемента массива ищем другой такой же элемент, у которого не совпадают индексы. Это очень просто, но очень неэффективно - квадратичное время и константные затраты памяти.
Можно чуть получше - догадаться, но в отсортированном массиве одинаковые элементы будут стоять рядом и нам нужно лишь найти тот, у которого нет пары. Время - O(nlogn), память - константная.
Можно еще лучше - закидывать элементы в хэш-мапу и потом пройтись по ней и найти то число, количество вхождений которого в массив - 1. Время линейное, затраты по памяти тоже линейные.
Но все это не удовлетворяет демоненка задачи. Ему хочется крови и константной памяти при линейном времени. Что же поможет удовлетворить его голод перед тем, как он набросится на пальцы?
Математика!
Не зря вчерашний пост был про операцию xor. Это была подводка к этой задаче.
Очевидным свойством операции xor над числами - xor двух одинаковых чисел дает ноль. И ксор любого числа с нулем в результате будет давать то же самое число.
Представим себе, что числа в нашем массиве расположены определенным образом - в начале идут парные числа, а в самом конце - наше одинокое число.
Тогда мы выставим результирующую переменную в ноль и будем ксорить по порядку все числа с этим результатом. Применяя эти два свойства мы получим следующее:
3 3 2 2 7 7 5
int res = 0;
res ^= 3; // res == 3
res ^= 3; // res == 0
res ^= 2; // res == 2
res ^= 2; // res == 0
res ^= 7; // res == 7
res ^= 7; // res == 0
res ^= 5; // res == 5
по итогу результат будет равен последнему числу, то есть нужному нам ответу.
"Но это же фигня какая-то. Порядок совсем не такой! Он может быть любым!"
Все верно. Однако мы добавляем в этот коктейль пару щепоточек свойства коммутативности xor и пару столовых ложек его ассоциативности (aka от перемены мест слагаемых сумма не меняется) и получим вкуснейшее решение. Как угодно переставляйте местами числа в массиве - результат будет ровно тот же по свойствам операции xor.
Тут можно такую аналогию провести. Вместо xor использовать операцию "+", а вместо одинаковых чисел - число и его отрицательный брат. Выглядеть это может так:
-3 + 1 + 5 + (-4) + 3 + (-1) + (-5)
У вас же не возникает сомнений, что результатом вычисления этого выражения будет -4. И я даже знаю, как вы это делаете. Находите противоположные числа, в уме зачеркиваете их и как бы зануляете их. По итогу остается сирота.
Ровно то же самое происходит и в нашей сегодняшней задаче.
Пока писал пост еще глубже понял прикол задачи. Она удивительно красивая! И подходит для решения разработчикам и энтузиастам разных уровней: начинающие решают за 2 цикла, продвинутые колдуют ксорами. Надеюсь, решение вам тоже понравилось)
Solve your problems. Stay cool.
