Single Number: как найти элемент без пары через XOR

Коротко

Все числа в массиве встречаются дважды, одно — один раз. Найти его можно за один проход и без дополнительной памяти: достаточно сложить всё через XOR. Вокруг этой идеи построено целое семейство задач:

Что такое AND, XOR и сдвиги, здесь не объясняю: всё это есть в статье про битовые операции. Здесь разберём, почему порядок элементов не влияет на ответ, что на самом деле лежит в переменной-аккумуляторе и где Python ведёт себя не как другие языки.

Сначала решаем в лоб

Первое, что приходит в голову, и именно с этого стоит начинать на собеседовании, — посчитать вхождения:

def single_by_dict(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
    for x, count in counts.items():
        if count == 1:
            return x


print(single_by_dict([4, 1, 2, 1, 2]))  # 4

Время $O(n)$, память $O(n)$. Подробнее о том, почему вставка и поиск тут в среднем стоят $O(1)$, — в статье про хеш-таблицы.

Счётчики здесь избыточны: нас интересует только «видели число нечётное число раз или нет». Поэтому хватит множества: увидели впервые — положили, увидели снова — убрали.

def single_by_set(nums):
    seen = set()
    for x in nums:
        if x in seen:
            seen.remove(x)
        else:
            seen.add(x)
    return seen.pop()


print(single_by_set([4, 1, 2, 1, 2]))  # 4

Ещё два варианта, которые стоит хотя бы назвать. Сортировка ставит пары рядом, и первая «сломанная» пара указывает на ответ, но это уже $O(n \log n)$ по времени. Арифметика: удвоенная сумма уникальных чисел минус сумма всех как раз и даст одинокое число.

def single_by_sort(nums):
    nums = sorted(nums)
    for i in range(0, len(nums) - 1, 2):
        if nums[i] != nums[i + 1]:
            return nums[i]
    return nums[-1]


def single_by_sum(nums):
    return 2 * sum(set(nums)) - sum(nums)


print(single_by_sort([4, 1, 2, 1, 2]))  # 4
print(single_by_sum([4, 1, 2, 1, 2]))  # 4

Следующий вопрос интервьюера предсказуем: а можно без дополнительной памяти?

Решение через XOR

Всё решение умещается в три строки:

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x
    return result


print(single_number([4, 1, 2, 1, 2]))  # 4
print(single_number([7]))  # 7
print(single_number([0, 3, 3]))  # 0

Обратите внимание на третий пример: ответом может быть и ноль. Ничего особого делать не нужно, но такой тест стоит проговорить вслух.

То же самое одной строкой, если в команде так принято:

from functools import reduce
from operator import xor


def single_number_short(nums):
    return reduce(xor, nums, 0)


print(single_number_short([4, 1, 2, 1, 2]))  # 4

А отрицательные числа?

В Python целые числа ведут себя как бесконечный дополнительный код: у отрицательного слева бесконечно много единиц. На Single Number это не влияет: хвосты единиц в паре тоже взаимно уничтожаются, а у одинокого отрицательного числа хвост сохранится, и знак выйдет правильным.

print(single_number([-3, 7, -3]))  # 7
print(single_number([2, -9, 2]))  # -9
print(single_number([-2147483648, 1, 1]))  # -2147483648

Почему порядок не важен

Обычно здесь говорят «пары сокращаются» и идут дальше. Но в массиве [4, 1, 2, 1, 2] пары не стоят рядом. Есть три способа убедиться, что это ни на что не влияет, и для понимания полезны все.

Алгебра

XOR обладает четырьмя свойствами:

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

На собеседовании этого доказательства достаточно. Сама программа ничего не переставляет, но результат у неё такой же, как у переставленной цепочки.

Чётность по столбцам

XOR работает с каждым битом независимо, и результат в одном разряде — это чётность количества единиц в этом разряде. Запишем числа столбиком:

4 = 100
1 = 001
2 = 010
1 = 001
2 = 010
-------
    100   единиц в столбцах: 1, 2, 2

Подсчёт единиц в столбце по определению не зависит от порядка строк. Такой же взгляд пригодится и дальше: Single Number II решается ровно этим подсчётом, только по модулю 3.

Что лежит в аккумуляторе

Промежуточные значения result выглядят как мусор:

Но у них есть точный смысл, и это инвариант цикла: result равен XOR тех чисел, которые к этому моменту встретились нечётное число раз. Это то же множество seen из решения выше, только сжатое в одно число. Восстановить из него элементы нельзя, зато в конце в нём остаётся ровно один элемент, а XOR одного элемента — он сам.

Поэтому XOR не «магия», а упаковка множества. Для порядка [1, 2, 4, 2, 1] промежуточные значения будут другими (1, 3, 7, 5, 4), конечный результат тот же.

Сколько памяти экономим на самом деле

$O(n)$ против $O(1)$ — это асимптотика (см. нотацию Big O). Посмотрим на настоящие цифры. Замеряю пик дополнительных аллокаций через tracemalloc:

import tracemalloc


def peak_kib(func, nums):
    tracemalloc.start()
    func(nums)
    _, peak = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return peak / 1024

Массив на 30 001 элемент (15 000 пар и одно одинокое), CPython 3.9. Сами числа хранит исходный список, поэтому в замер попадает только то, что создаёт функция.

На других версиях CPython цифры будут немного другими, порядок останется.

Здесь видно то, чего не показывает асимптотика:

• Множество чувствительно к порядку. Если пары стоят рядом, в нём в любой момент лежит не больше одного элемента. Если вперемешку или «сначала все по разу» — таблица разрастается до тысяч элементов. Худший случай всё равно $O(n)$, но реальный расход зависит от данных.
• Словарь и set(nums) платят за все различные значения всегда, порядок им не важен.
• XOR не зависит ни от чего. Одна переменная, и она никогда не длиннее самого длинного числа из массива.

По времени разница скромнее. На том же массиве цикл с XOR занял около 0,7 мс, а словарь — около 1,8 мс. Варианты с sum и с reduce уложились примерно в 0,5 мс: они работают на C, а не в цикле интерпретатора. Так что в Python XOR выигрывает прежде всего памятью.

Когда словарь всё-таки лучше

XOR молча верит условию. Если данные нарушают его, ответ будет правдоподобным и неверным:

print(single_number([1, 1, 5, 7]))  # 2
print(single_number([5, 5, 5, 2]))  # 7

В первом случае одиноких два, и мы получили 2, которого в массиве вообще нет. Во втором одно число встречается трижды, результат тоже бессмысленный. Со словарём нарушение хотя бы видно: можно посмотреть на счётчики и сообщить об ошибке. Если вход приходит извне, а память не критична, счётчики надёжнее.

Single Number II: остальные встречаются трижды

Пример выше показывает, почему XOR здесь бесполезен: нечётное число вхождений не сокращается. Но идея со столбцами работает. Если все числа, кроме одного, встречаются трижды, то количество единиц в каждом разряде кратно 3, а одинокое число добавляет остаток.

Разберём [2, 2, 3, 2]: в нулевом бите единица одна (у тройки), остаток 1. В первом бите единиц четыре, остаток 1. Получаем 11 = 3.

Прямой перевод этой идеи на Python содержит ошибку:

def single_number_ii_buggy(nums):
    result = 0
    for bit in range(32):
        ones = sum((x >> bit) & 1 for x in nums)
        if ones % 3:
            result |= 1 << bit
    return result


print(single_number_ii_buggy([2, 2, 3, 2]))  # 3
print(single_number_ii_buggy([-5, -1, -1, -1]))  # 4294967291

Чтение битов тут корректно: >> у отрицательного числа подтягивает слева единицы, а & 1 берёт нужный разряд. Проблема в сборке ответа. В Python нет 32-битного int, и единица в бите 31 — это просто слагаемое $2^{31}$, а не знак. Получилось $2^{32} - 5$: те же биты, что у $-5$, прочитанные как беззнаковое число.

Лечится переводом вручную. Условия LeetCode 137 ограничивают значения диапазоном от $-2^{31}$ до $2^{31}-1$, так что вычитаем $2^{32}$, если поднят старший бит:

def single_number_ii(nums):
    result = 0
    for bit in range(32):
        ones = sum((x >> bit) & 1 for x in nums)
        if ones % 3:
            result |= 1 << bit
    # Бит 31 в дополнительном коде означает знак, а Python об этом не знает
    if result >= 1 << 31:
        result -= 1 << 32
    return result


print(single_number_ii([2, 2, 3, 2]))  # 3
print(single_number_ii([-5, -1, -1, -1]))  # -5
print(single_number_ii([-2147483648, 8, 8, 8]))  # -2147483648

В JavaScript такой поправки нет: побитовые операторы там сами приводят результат к знаковому int32. В Java и C++ int такой же знаковый 32-битный тип.

function singleNumberII(nums) {
  let result = 0
  for (let bit = 0; bit < 32; bit++) {
    let ones = 0
    for (const x of nums) ones += (x >> bit) & 1
    if (ones % 3) result |= 1 << bit
  }
  return result
}

console.log(singleNumberII([-5, -1, -1, -1])) // -5

Память $O(1)$: одна переменная и счётчик. Время — 32 прохода по массиву, то есть $O(32n)$, формально $O(n)$. Та же схема работает для любого $k$, пока число вхождений одинокого элемента не кратно $k$:

def single_among_k(nums, k):
    result = 0
    for bit in range(32):
        if sum((x >> bit) & 1 for x in nums) % k:
            result |= 1 << bit
    return result - (1 << 32) if result >= 1 << 31 else result


print(single_among_k([9, 9, 9, 9, 9, -4], 5))  # -4

Без 32 проходов: автомат на двух переменных

Подсчёт можно вести сразу по всем разрядам параллельно. Каждому биту нужен счётчик по модулю 3, то есть два бита состояния. Заведём две переменные: в ones хранится младший бит каждого счётчика, в twos — старший.

Третья единица возвращает разряд в 00. Переход записывается двумя строками:

def single_number_ii_fsm(nums):
    ones = twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos
        twos = (twos ^ x) & ~ones
    return ones


print(single_number_ii_fsm([2, 2, 3, 2]))  # 3
print(single_number_ii_fsm([-5, -1, -1, -1]))  # -5

Порядок строк важен: вторая использует уже новое значение ones. Прогоните один разряд с тремя единицами подряд: состояние (twos, ones) пройдёт 00 → 01 → 10 → 00. В конце в ones остаются те разряды, где остаток равен 1, а это и есть биты ответа.

Самое приятное для Python: поправка знака здесь не нужна. Бесконечный хвост отрицательного числа проходит через тот же автомат, что и остальные разряды, поэтому в конце у ones хвост единиц будет только при отрицательном ответе. Заодно исчезает ограничение на 32 разряда, из-за которого single_number_ii молча теряет старшие биты:

print(single_number_ii([2**40, 7, 7, 7]))  # 0
print(single_number_ii_fsm([2**40, 7, 7, 7]))  # 1099511627776

Если интервьюер не просит иного, начинайте с подсчёта битов: его легче объяснить и труднее написать с ошибкой. Автомат — приятный бонус, если останется время.

Single Number III: два одиноких элемента

Теперь без пары остаются два числа, $a$ и $b$. XOR всего массива даст $a \oplus b$, и разделить эту смесь напрямую нельзя. Но кое-что о ней известно: $a \neq b$, значит, результат ненулевой. А каждая единица в нём — это разряд, в котором $a$ и $b$ различаются.

Возьмём любой такой разряд и разделим весь массив на две группы: у кого он равен 1 и у кого 0.

• $a$ и $b$ попадут в разные группы: в этом разряде они различаются.
• Оба элемента любой пары попадут в одну группу: числа одинаковые, разряд тоже.

Получается две обычных задачи Single Number. Удобнее всего брать младший единичный бит: его даёт diff & -diff (откуда это берётся, есть в статье про биты).

def single_number_iii(nums):
    diff = 0
    for x in nums:
        diff ^= x

    low = diff & -diff

    a = 0
    for x in nums:
        if x & low:
            a ^= x

    return [a, a ^ diff]


print(single_number_iii([1, 2, 1, 3, 2, 5]))  # [3, 5]
print(single_number_iii([-1, -1, -2147483648, 2147483647]))  # [2147483647, -2147483648]

Заметьте: вторую группу считать незачем. Раз diff = a ^ b, то b = a ^ diff.

Разбор на [1, 2, 1, 3, 2, 5]:

diff = 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = 110
low  = 010

есть бит 010: 2, 3, 2  ->  XOR = 3
нет бита 010: 1, 1, 5  ->  XOR = 5

В Python low всегда положительный. В языках с 32-битным int это не так: если $a$ и $b$ различаются только знаковым битом, low окажется равен минимальному int32, поэтому проверять условие надо через !== 0, а не через > 0:

const diff = 0 ^ -2147483648
const low = diff & -diff

console.log(low) // -2147483648
console.log((-2147483648 & low) > 0) // false
console.log((-2147483648 & low) !== 0) // true

Missing Number: та же задача в маскировке

Массив длины $n$ содержит различные числа из диапазона от $0$ до $n$, одно пропало. Найти его.

Приём такой: припишем к массиву все числа от $0$ до $n$. Тогда каждое присутствующее число встречается дважды, а пропавшее один раз. Это Single Number. Массив даже не нужно дополнять: индексы $0..n-1$ уже есть, остаётся добавить только $n$:

def missing_number(nums):
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result


print(missing_number([3, 0, 1]))  # 2
print(missing_number([0]))  # 1
print(missing_number([1]))  # 0

На примере [3, 0, 1]: сворачиваем 3 ^ (0 ^ 3) ^ (1 ^ 0) ^ (2 ^ 1). Все числа, кроме двойки, встречаются дважды.

Честно говоря, в Python проще и понятнее через формулу суммы арифметической прогрессии:

def missing_number_sum(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)


print(missing_number_sum([3, 0, 1]))  # 2

У XOR здесь есть преимущество только в языках с фиксированными целыми. Произведение $n(n+1)$ выходит за пределы int32 уже при $n \ge 46341$, а XOR переполниться не может: результат не длиннее самого большого операнда. На собеседовании назовите оба варианта и скажите об этой разнице.

Типичные ошибки

• Считать условие гарантированным там, где оно не гарантировано. На [1, 1, 5, 7] или [5, 5, 5, 2] XOR вернёт число без смысла и без ошибки. Если данные внешние, нужны счётчики.
• Забыть про знак в Python. Счёт битов без поправки вернёт 4294967291 вместо -5. Тесты только с положительными числами этого не покажут.
• Сравнивать с единицей. (x & low) == 1 неверно: при поднятом бите выражение равно самому low, а не единице. Сработает только при low = 1, поэтому часть тестов может пройти. Правильно проверять на ненулевое значение.
• Забыть про приоритет операторов. В JavaScript, Java и C++ == связывает сильнее &, поэтому x & low == 0 читается как x & (low == 0), а в Java такое и вовсе не скомпилируется. В Python наоборот. Ставьте скобки всегда.
• Вызывать reduce без начального значения. На пустом списке reduce(xor, []) бросит TypeError. По условию массив не пуст, но reduce(xor, nums, 0) ничего не стоит.
• Перепутать строки в автомате. В single_number_ii_fsm twos вычисляется уже по новому ones. Параллельное присваивание через кортеж сломает переходы.

Как это проходит на собеседовании

Задача короткая, поэтому ценность ответа не в коде, а в объяснении. Рабочий сценарий:

1. Назовите решение со словарём и его оценку: $O(n)$ по времени и памяти.
2. Заметьте, что счётчик не нужен, важна только чётность. Отсюда множество, а от множества мост к XOR.
3. Напишите три строки и докажите: коммутативность, ассоциативность, $a \oplus a = 0$. Инвариант про нечётные вхождения покажет, что вы понимаете механику, а не помните трюк.
4. Проговорите граничные случаи: один элемент, ответ ноль, отрицательные числа.
5. Назовите, что произойдёт при нарушении условия.

Логичное продолжение — «а если остальные встречаются трижды?» или «а если одиноких два?». Поэтому Single Number II и III стоит держать наготове, а если вы пишете на Python — сразу сказать про знак.

Задачу из статьи можно решить прямо на сайте: она в блоке «Задачи по теме» ниже. Если готовитесь по массивам в целом, загляните в разбор типовых задач на массивы.

Что запомнить

• XOR считает чётность в каждом разряде отдельно, поэтому порядок элементов не важен.
• В аккумуляторе лежит XOR чисел, встреченных нечётное число раз, — это сжатое множество.
• Множество и словарь расходуют сотни килобайт на 30 тысячах элементов, XOR — одну переменную. Цена — полное доверие к условию.
• Трижды: считаем биты по модулю 3, в Python вручную переводим бит 31 в знак либо берём автомат ones/twos.
• Два одиноких: XOR всего, младший единичный бит, разбиение на две группы.
• Missing Number сводится к Single Number приписыванием диапазона.