Задача. Единственный элемент

Дан целочисленный массив nums. Каждый элемент встречается трижды, кроме одного, который встречается ровно один раз.

Необходимо найти этот единственный элемент.

Дополнительно: попробуйте реализовать алгоритм с линейной сложностью и с константной сложностью по памяти.

Пример

nums = [2,2,3,2]
Output: 3

Разбор

Для решения задачи за константное время используется метод побитовых операций для отслежвания количества каждой битовой позиции. Используя побитовые операции можно найти биты, которые появлялись один, две или три раза.

Алгоритм

1. Заведем 2 переменные, single, twice - для отслеживания количества каждой позиции бита.

single - отслеживает биты, появившиеся один раз
twice - отслеживает биты, появившиеся дважды

2. Запускаем цикл по исходному массиву.

single = (single ^ num) & ~twice

single ^ num: выполняет XOR текущего числа i с предыдущим значением единиц. Эта операция переключает биты, появившиеся нечетное число раз, оставляя неизменными биты, появившиеся дважды.
(~twice) делает флип битов в twice, фактически исключая из рассмотрения биты, появившиеся дважды.
Операция & обеспечивает сохранение только тех битов, которые появились один раз (после XOR), а не два раза (после ~twice).

twice = (twice ^ num) & ~single

twice ^ num: выполняет XOR текущего числа i с предыдущим значением twice. Эта операция переключает биты, появившиеся четное число раз, удаляя биты, появившиеся дважды.
(~single) делает флип битов в single, фактически исключая из рассмотрения биты, появившиеся один раз.
Операция & обеспечивает сохранение только тех битов, которые появились дважды (после XOR), а не один раз (после ~single).

3. После прохождения всех чисел значение, хранящееся в single, будет представлять единственное число, которое встречается в массиве только один раз.

P.S.

Когда бит появляется в первый раз (single = 0 и бит переключается), он сохраняется в единицах.
Когда бит появляется во второй раз (single = 1 и бит переключается), он удаляется из единиц и сохраняется в двойках.
Когда бит появляется в третий раз (single = 0 и бит переключается), он удаляется и из единиц, и из двоек.
К концу итерации биты, оставшиеся в единицах, представляют собой биты единственного числа, появившиеся только один раз.

Реализация

public int SingleNumber(int[] nums) {
    int single = 0;
    int twice = 0;

    foreach (int num in nums)
    {
        single = (single ^ num) & ~twice;
        twice = (twice ^ num) & ~single;
    }

    return single;
}

https://gist.github.com/unilecs/474684d932992f3d4a684811a5d0b938

Play-test

https://dotnetfiddle.net/QqS4Gz