Решение любопытной цепочки задач c leetcode или сеанс древней алгоритмической магии с последующим разоблачением

Мы воспользуемся свойством функции XOR давать 1 только в том случае, когда оба ее операнда неравны друг другу.

Пройдя по всем элементам массива и делая им побитовый xor мы сведем к нулю все одинаковые значения битов, а в результате, то что останется и будет искомым результатом.

Вот короткий код решения на python3:

def single_number_i(nums: list) -> int:

    result = 0

    for el in nums:

        result ^= el

    return result

Мы используем всего лишь столько дополнительной памяти, сколько занимает int и находим решение за единственный проход по заданному массиву, что дает нам O(n) по сложности. Это чистое и красивое решение.

К сожалению, мы не можем воспользоваться предыдущим трюком, так как в данном случае мы не сможем превратить парные биты в нужной позиции в нули. Было бы заманчиво привести данный нам массив к виду из предыдущей задачи, а затем решить его аналогичным способом. Рассуждая таким образом, можно легко заметить, что если бы мы знали, что пробегая по массиву мы уже встречали число N дважды(ну или трижды), то мы могли бы добавить к получаемой нами сумме дополнительный XOR с N, сделав итоговое число XOR c этим числом четным, таким образом убрав его из итоговой суммы, а то что останется и будет нашим ответом.

def single_number_ii(nums: list) -> int:

    mem = {}

    result = 0

    for el in nums:

        if not mem.get(el, False):

            mem[el] = 1

        else:

            mem[el] += 1

            if mem[el] == 2:

                result ^= el

        result ^= el

    return result

К сожалению, максимально это решение потребует (len(nums)-1)/3 по памяти, что нельзя назвать константным потреблением, так что придется нам искать другое решение.

Попробуем поменять наш подход. Если мы сможем встречая число первый раз класть его в ответ, встречая второй раз - класть в аккумулятор и встречая  третий раз обнулять и ответ и аккумулятор, то это бы помогло нам решить задачу за один проход по списку с потреблением дополнительной памяти ровно в два int’a, что соответствует требованию задачи. Итак, снова применим немного побитовой магии:

def single_number_137_ii(nums: list) -> int:

    ans, acc = 0, 0

    for n in nums:

        ans = ans ^ n & ~acc

        acc = acc ^ n & ~ans

    return ans

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

Очевидно, что мы легко сможем убрать все парные числа обычным xor-ом, как мы сделали это во время решении первой задачи. Тогда вся сложность задачи заключается в выявлении любого из уникальных чисел, тогда второе легко можно будет вычислить посчитав xor между этим числом и нашей xor-суммой. 

Для этого нам нужно найти достаточно найти любой отличающийся бит между этими уникальными числами, а затем снова пройти по массиву, сделав суммирование по xor, разделив результаты на две группы - для чисел, где этот бит установлен и для тех, где он равен 0. В результате мы и получаем искомые уникальные элементы.

def single_number_260(nums: list) -> int:

    res1, res2 = 0, 0

    glob_xor = 0

    for n in nums:

        glob_xor ^= n

    diff_bit = glob_xor & ~(glob_xor + 1)

    for n in nums:

        if n & diff_bit:

            res1 ^= n

        else:

            res2 ^= n

    return [res1, res2]

Несмотря на то, что нам пришлось пройти массив 2 раза, это по прежнему O(n) по сложности и всего 2 int’a по памяти.