Битовые манипуляции

O(1)/O(n)

Рассматривайте целое число как ряд включённых/выключенных битов и переключайте, проверяйте или комбинируйте их через &, |, ^, ~ и сдвиги. Маска, число с одним установленным битом, нацеливается точно на нужный бит.

Сигналы

найти единственное или уникальное число через XORустановить, снять, переключить или проверить битупаковать много флагов да/нет в одно целое числоподсчёт установленных битов или проверка степени двойки

Шаблон

function findUnique(nums) {
    return nums.reduce((acc, n) => acc ^ n, 0);
}
function setBit(mask, i) { return mask | (1 << i); }
function clearBit(mask, i) { return mask & ~(1 << i); }
function hasBit(mask, i) { return (mask & (1 << i)) !== 0; }

Похоже, но не то

Хеш-множество / хеш-карта: Хеш-множество может отслеживать, какие значения уже встречались, но это стоит O(n) дополнительной памяти. Когда значения это небольшие флаги, или все числа кроме одного встречаются дважды, упаковка их в одно целое число и XOR или маски дают тот же ответ за O(1) памяти без выделения множества.

значения помещаются в фиксированное 32/64-битное слово, один проход по битам или массиву -> O(1) на битовый трюк над одним словом, O(n) на XOR/маски по всему массиву.

Изучить этот паттерн