RUВход: две программы, обе правильные
В массиве миллион чисел; сколько в нём пар с суммой 100? Наивный ход — два вложенных цикла: пар около $5\cdot10^{11}$, программа считает часами. Умный — один проход, на каждом шаге один вопрос счётчику: сколько раз уже встречалось $100 - x$; это $10^{6}$ шагов, доли секунды. Обе программы верны математически, но досчитает одна. Весь день про то, как за полминуты понять по формулировке, какая из двух у тебя в голове, и как вторую написать без ошибок на границах.
Python в объёме дня
a = [3, 1, 4, 1, 5]
a[0], a[-1], a[1:4] # 3 5 [1, 4, 1] — с нуля, правый конец не входит
sum(1 for v in a if v > 3) # 2 — счёт по условию
sorted(a, reverse=True)[:3] # [5, 4, 3]
7 // 2, 7 % 2, -(-7 // 2) # 3 1 4 — нацело, остаток, округление ВВЕРХ
5 ^ 3, 5 >> 1, 5 & 1 # 6 2 1 — XOR, сдвиг вправо, младший бит
s = set(a); 3 in s # {1, 3, 4, 5}; True — только «есть или нет»
from collections import Counter
c = Counter(a); c[1], c[42] # 2 0 — отсутствующий ключ даёт ноль, а не ошибку
import heapq; heapq.nlargest(3, a) # [5, 4, 3] без полной сортировки
for i, v in enumerate(a): pass # индекс и значение сразуДве строки отсюда важны отдельно: -(-p // k) — округление вверх без модуля math (деление нацело округляет вниз), а Counter даёт ноль для отсутствующего ключа, поэтому приёмы ниже пишутся без проверки if key in d.
Сколько операций ты можешь себе позволить
Считать надо не секунды, а число операций: секунды зависят от машины, число операций — только от алгоритма и размера входа $n$.
| Сложность | $n = 10^{3}$ | $n = 10^{5}$ | $n = 10^{6}$ |
|---|
| $O(n)$ | $10^{3}$ | $10^{5}$ | $10^{6}$ |
| $O(n\log n)$ | $10^{4}$ | $1.7\cdot10^{6}$ | $2\cdot10^{7}$ |
| $O(n^{2})$ | $10^{6}$ | $10^{10}$ | $10^{12}$ |
Ориентир: компилируемый язык делает порядка $10^{8}$ простых операций в секунду, Python — на порядок-полтора меньше. Значит $10^{10}$ операций это около двух минут даже в хорошем случае, а $10^{12}$ — около трёх часов.
Ограничение в условии — это подсказка про сложность$n \le 10^{3}$ — квадратичный алгоритм пройдёт. $n \le 10^{6}$ — нужен один проход, сортировка или логарифм. $n \ge 10^{7}$ — только один проход. Читай ограничение до того, как придумывать решение: оно почти всегда называет приём.
| Структура | Быстро | Медленно или нельзя | Когда брать |
|---|
list | индекс, добавление в конец | поиск значения — $O(n)$ | нужен порядок и индексы |
set | проверка «есть ли», вставка — $O(1)$ | нет порядка и индексов | нужен только факт наличия |
dict | поиск по ключу, вставка — $O(1)$ | нет порядка по значению | нужно сопоставить ключу число |
куча (heapq) | достать минимум — $O(\log n)$ | искать произвольный элемент | нужны $k$ крайних из $n$ |
Множество и словарь платят за скорость памятью — в несколько раз больше, чем список. Формулировка для собеседования: «поиск за $O(1)$ в среднем, потому что хеш ведёт сразу в нужную ячейку; плата — память».
Приём 1. Хеш-таблица «видел раньше»
Two Sum. Есть ли в массиве пара с суммой target? Наивно — для каждого элемента искать пару справа, это все пары. Умно — держать множество seen уже пройденных и проверять target - x in seen: один проход вместо двух вложенных циклов. Вся идея в перемене вопроса: не «найдётся ли дальше», а «было ли раньше».
Если спрашивают, сколько таких пар, множество не годится: оно помнит факт, а не количество. Нужен счётчик:
from collections import Counter
seen = Counter(); cnt = 0
for x in a:
cnt += seen[target - x] # сколько подходящих уже было
seen[x] += 1«Найти пару» — множество, «посчитать пары» — счётчик. Перепутанная развилка даёт заниженный ответ без сигнала об ошибке, и она же решает исход финала y1101. Сам вопрос счётчику меняется от задачи к задаче: «сколько раз уже встречалось $10 - x$» в b1101, «сколько прежних префиксов равны $S_r - 36$» в b1104, «сколько прежних префиксов дают тот же остаток» в y1101. Вопрос разный, проход один и тот же.
Приём 2. Префиксные суммы
Заводим накопитель $S_0 = 0$, $S_k = a_1 + \cdots + a_k$ одним циклом pre.append(pre[-1] + v). Тогда сумма отрезка — одна разность, дословно как в формуле Ньютона — Лейбница: сумма элементов с индексами от $l$ до $r$ включительно равна $S_{r+1} - S_l$. Для $a = [4, 1, 6, 2, 5]$ выходит $S = [0, 4, 5, 11, 13, 18]$, и сумма элементов с индексами от 1 до 3 равна $S_4 - S_1 = 13 - 4 = 9$, то есть $1 + 6 + 2$.
Остатки — главный поворот темы. Сколько подотрезков имеют сумму, кратную $k$? Сумма отрезка это $S_r - S_l$, а по пункту блока «Мост» она делится на $k$ ровно тогда, когда $S_r$ и $S_l$ дают одинаковый остаток. Вопрос про отрезки стал вопросом про пары префиксов с равным остатком — а такие пары считает счётчик из приёма 1:
from collections import Counter
c = Counter({0: 1}) # пустой префикс тоже участвует
s = 0; total = 0
for v in a:
s = (s + v) % k
total += c[s] # все прежние префиксы с тем же остатком
c[s] += 1Проверим руками: $a = [3, 1, 4, 1, 5]$, $k = 3$. Префиксы $[0, 3, 4, 8, 9, 14]$, остатки $[0, 0, 1, 2, 0, 2]$. Остаток 0 встретился трижды — это $\binom{3}{2} = 3$ пары, остаток 2 дважды — ещё одна, остаток 1 — ни одной. Итого 4, и перебор всех пятнадцати подотрезков даёт те же 4.
c[0] = 1 — не украшениеПустой префикс $S_0 = 0$ обязан лежать в счётчике до начала цикла, иначе потеряются все подотрезки, начинающиеся с первого элемента. Код выглядит правильным, ответ просто занижен, и без разбора причину не видно. Это ошибка номер один темы.
Кадане — тот же вопрос к прошлым префиксам. Максимальная сумма подотрезка с правым концом $r$ равна $S_r - \min_{l < r} S_l$, поэтому хватает бегущего минимума вместо перебора пар. В обычной записи это две строки: cur = max(v, cur + v) и best = max(best, cur) при начальных best = cur = a[0], где cur — лучшая сумма подотрезка, кончающегося на текущем элементе, а выбор внутри max — решение «оставить левую границу или перенести её сюда». На массиве $[5, -2, -6, 7, -1, 4]$ значения cur идут $5, 3, -3, 7, 6, 10$, максимум 10 — это отрезок $[7, -1, 4]$, и перебор всех 21 подотрезка даёт то же. Начальное best = 0 вместо a[0] — главная ловушка приёма: на одних отрицательных числах такой код вернёт ноль.
Приём 3. Два указателя и окно
Встречное движение. На отсортированном массиве пара с заданной суммой ищется двумя указателями с концов: сумма мала — двигаем левый вправо, велика — правый влево. Это $O(n\log n)$ из-за сортировки, дороже хеш-множества, зато без лишней памяти.
Окно постоянной длины. Самый простой случай: длина окна задана числом, границы двигаются на каждом шаге вместе, а сумма нового окна берётся из старой за два действия — прибавить пришедший справа элемент, вычесть ушедший слева (w1103). Полный пересчёт стоил бы $O(nk)$, сдвиг стоит $O(n)$ при любой длине окна.
Окно переменной длины. Оба указателя идут в одну сторону: правый расширяет отрезок, левый догоняет, когда условие сломалось. Самый длинный подотрезок с суммой не больше 9 в массиве $[6, 1, 2, 3, 1, 7, 2, 4]$:
a = [6, 1, 2, 3, 1, 7, 2, 4]
s = 0; left = 0; best = 0
for right, v in enumerate(a):
s += v
while s > 9: # условие сломалось — двигаем левую границу
s -= a[left]; left += 1
best = max(best, right - left + 1)
print(best) # 4Ответ 4 — отрезок $[1, 2, 3, 1]$ с суммой 7; перебор всех 36 подотрезков даёт то же, но окно делает один проход.
Почему окно линейноКаждый из двух указателей проходит массив ровно один раз и никогда не идёт назад, поэтому шагов не больше $2n$, сколько бы раз внутренний while ни срабатывал. Это же единственное, что можно сломать: стоит левой границе прыгнуть назад, как правильность и линейность исчезают одновременно.
Когда условие окна не про сумму, а про состав («все символы различны», «не больше двух разных букв»), состояние держат в словаре: символ и его последний индекс либо число вхождений.
Приём 4. Бинарный поиск по ответу
По отсортированному массиву элемент ищут делением пополам за $\log_2 n$ шагов. Но на экзамене чаще встречается другой поворот: ищут не элемент массива, а само число ответа. Признак — «минимальное такое, что» или «максимальное такое, что» плюс лёгкая проверка конкретного значения. Пример. Наименьшее целое $x$, у которого $x^{2} \ge 3000$. Предикат — это x * x >= 3000, и он монотонен: годится $x$ — годится и любое большее. Значит годные значения образуют луч, и нужна его левая граница.
lo, hi = 1, 3000 # hi заведомо годится
while lo < hi:
mid = (lo + hi) // 2
if mid * mid >= 3000: hi = mid # годится — граница не правее mid
else: lo = mid + 1 # не годится — mid точно мал
print(lo) # 55 за 12 шагов вместо 3000 проверокПроверка соседа: $55^{2} = 3025 \ge 3000$, а $54^{2} = 2916 < 3000$ — значит 55 именно граница.
Шаблон запоминается дословноwhile lo < hi, внутри hi = mid и lo = mid + 1, ответ в lo. Инвариант: hi всегда «годится», lo — левый край области поиска; отрезок каждый шаг строго укорачивается, поэтому зацикливания нет.
Для «максимальное такое, что» шаблон зеркальный: mid = (lo + hi + 1) // 2, внутри lo = mid и hi = mid - 1, ответ снова в lo. С обычной серединой он зацикливается на паре соседей — классическая ловушка. И ещё два места, где верная идея даёт неверное число: границы взяты узко, так что ответ вне отрезка, и предикат немонотонен — тогда приём неприменим вообще.
Приём 5. Числа поразрядно
XOR (^) складывает двоичные записи поразрядно и без переноса: $1 \oplus 1 = 0$, $1 \oplus 0 = 1$, $0 \oplus 0 = 0$. Например $22 \oplus 13$: записи $10110$ и $01101$ дают $11011 = 27$. Отсюда два равенства, на которых стоят все задачи про XOR: $x \oplus x = 0$ и $x \oplus 0 = x$; в цепочке всё, что встретилось дважды, гасится само.
Второй факт — про сравнение по разрядам. По пункту блока «Мост» один старший разряд больше суммы всех младших, поэтому варианты сравнивают начиная со старшего бита: выигрыш там перевешивает любой проигрыш во всех младших вместе взятых. На этом и стоит замена перебора пар спуском по дереву двоичных записей — то же деление пополам, что и в приёме 4, только режется множество кандидатов по очередному биту.
Отсюда правило для пар. Нужен максимальный XOR — на каждом разряде, начиная со старшего, ищи партнёра с противоположным битом (b1105); нужен минимальный — партнёра с таким же (s1101). У минимума есть ещё одно следствие того же факта: он всегда достигается на паре соседей в отсортированном порядке, то есть на маленьких данных хватает $n - 1$ проверки вместо всех пар.
Скрытые $O(n^{2})$ в Pythonresult += ch в цикле не дописывает символ, а копирует всю строку целиком: строки неизменяемы, и внешне линейный код оказывается квадратичным. Лечится накоплением в список и "".join(parts) в конце. Ловушка живучая: код проходит на маленьком тесте и упирается в предел на большом.
Что должно остаться в голове
- Ограничение в условии называет допустимую сложность; $10^{12}$ операций — это часы.
list — порядок и индексы; set и dict — мгновенный поиск за счёт памяти; куча — $k$ крайних.- «Было ли раньше» вместо «найдётся ли дальше»: множество для факта, счётчик для количества.
- Сумма отрезка — разность двух префиксов; «делится на $k$» — равенство остатков;
c[0] = 1. - Кадане — тот же вопрос к прошлым префиксам, только про минимум, а не про равенство.
- Окно линейно потому, что обе границы идут только вперёд; длина окна либо задана числом, либо задана условием.
- «Минимальное такое, что» плюс лёгкая проверка — бинарный поиск по ответу; шаблон
hi = mid и lo = mid + 1, потом проверка соседа. - $x \oplus x = 0$; старший разряд перевешивает все младшие вместе взятые: для максимума XOR партнёр с противоположным битом, для минимума — с таким же.
ENOpening: two programs, both mathematically correct
An array contains a million numbers; how many pairs sum to 100? The naive approach uses two nested loops: roughly $5\cdot10^{11}$ pairs, so the program runs for hours. The smart approach makes one pass and asks the counter one question at every step: how many times has $100 - x$ already appeared? That is $10^{6}$ steps, or a fraction of a second. Both programs are mathematically correct, but only one will finish. The whole day is about recognizing within half a minute which of the two you have in mind, then writing it without edge-case mistakes.
Python for today
a = [3, 1, 4, 1, 5]
a[0], a[-1], a[1:4] # 3 5 [1, 4, 1] — zero-based; the right endpoint is excluded
sum(1 for v in a if v > 3) # 2 — count by condition
sorted(a, reverse=True)[:3] # [5, 4, 3]
7 // 2, 7 % 2, -(-7 // 2) # 3 1 4 — floor division, remainder, CEILING
5 ^ 3, 5 >> 1, 5 & 1 # 6 2 1 — XOR, right shift, least significant bit
s = set(a); 3 in s # {1, 3, 4, 5}; True — only “present or absent”
from collections import Counter
c = Counter(a); c[1], c[42] # 2 0 — a missing key returns zero, not an error
import heapq; heapq.nlargest(3, a) # [5, 4, 3] without a full sort
for i, v in enumerate(a): pass # index and value at onceTwo lines here deserve special attention: -(-p // k) computes a ceiling without importing math (integer division rounds down), while Counter returns zero for a missing key, so the techniques below need no if key in d check.
How many operations can you afford?
Count operations rather than seconds: seconds depend on the machine, but the operation count depends only on the algorithm and input size $n$.
| Complexity | $n = 10^{3}$ | $n = 10^{5}$ | $n = 10^{6}$ |
|---|
| $O(n)$ | $10^{3}$ | $10^{5}$ | $10^{6}$ |
| $O(n\log n)$ | $10^{4}$ | $1.7\cdot10^{6}$ | $2\cdot10^{7}$ |
| $O(n^{2})$ | $10^{6}$ | $10^{10}$ | $10^{12}$ |
A rule of thumb: a compiled language performs around $10^{8}$ simple operations per second; Python does an order of magnitude to an order and a half fewer. So $10^{10}$ operations take about two minutes even in a good case, while $10^{12}$ take roughly three hours.
The constraint in the statement is a complexity hint$n \le 10^{3}$—a quadratic algorithm will pass. $n \le 10^{6}$—you need one pass, a sort, or a logarithm. $n \ge 10^{7}$—only one pass. Read the constraint before inventing a solution: it almost always names the technique.
| Structure | Fast | Slow or unavailable | When to use it |
|---|
list | indexing, appending | value lookup—$O(n)$ | you need order and indices |
set | membership check, insertion—$O(1)$ | no order or indices | you only need presence/absence |
dict | key lookup, insertion—$O(1)$ | no ordering by value | you need to map a key to a number |
heap (heapq) | extract the minimum—$O(\log n)$ | arbitrary-element lookup | you need the $k$ extremes among $n$ |
Sets and dictionaries trade memory for speed, using several times more memory than a list. An interview-ready phrasing is: “Average $O(1)$ lookup, because the hash points straight to the right bucket; the cost is memory.”
Technique 1. Hash table: “seen before”
Two Sum. Does an array contain a pair whose sum is target? Naively, for each element you search to its right, which visits all pairs. The smart approach keeps a set seen of elements already passed and checks target - x in seen: one pass instead of two nested loops. The whole idea is to change the question from “will it appear later?” to “did it appear earlier?”
If the question asks how many such pairs there are, a set is not enough: it remembers a fact, not a count. You need a counter:
from collections import Counter
seen = Counter(); cnt = 0
for x in a:
cnt += seen[target - x] # how many matching values have appeared
seen[x] += 1“Find a pair” means a set; “count pairs” means a counter. Mixing up this fork silently undercounts the answer, and it is exactly what decides final y1101. The question asked of the counter changes from problem to problem: “how many times has $10 - x$ appeared” in b1101, “how many previous prefixes equal $S_r - 36$” in b1104, and “how many previous prefixes have the same remainder” in y1101. The question changes; the pass is the same.
Technique 2. Prefix sums
Define an accumulator $S_0 = 0$, $S_k = a_1 + \cdots + a_k$ in one loop, pre.append(pre[-1] + v). Then a segment sum is one difference, exactly as in Newton–Leibniz: the sum of elements with indices $l$ through $r$ inclusive is $S_{r+1} - S_l$. For $a = [4, 1, 6, 2, 5]$, we get $S = [0, 4, 5, 11, 13, 18]$, and the sum of indices 1 through 3 is $S_4 - S_1 = 13 - 4 = 9$, namely $1 + 6 + 2$.
Remainders are the key turn. How many subarrays have a sum divisible by $k$? A segment sum is $S_r - S_l$, and the “Bridge” fact says it is divisible by $k$ exactly when $S_r$ and $S_l$ have the same remainder. A question about segments becomes a question about pairs of prefixes with equal remainders—and the counter from technique 1 counts those pairs:
from collections import Counter
c = Counter({0: 1}) # the empty prefix participates too
s = 0; total = 0
for v in a:
s = (s + v) % k
total += c[s] # all previous prefixes with the same remainder
c[s] += 1Check it by hand: $a = [3, 1, 4, 1, 5]$, $k = 3$. Prefixes are $[0, 3, 4, 8, 9, 14]$, with remainders $[0, 0, 1, 2, 0, 2]$. Remainder 0 appears three times, giving $\binom{3}{2} = 3$ pairs; remainder 2 appears twice, giving one more; remainder 1 gives none. The total is 4, and enumerating all fifteen subarrays gives the same result.
c[0] = 1 is not decorationThe empty prefix $S_0 = 0$ must be in the counter before the loop begins, or every subarray starting at the first element is lost. The code looks right, the answer is merely too small, and the cause is invisible without a walkthrough. This is topic mistake number one.
Kadane’s algorithm asks the same question of earlier prefixes. The maximum subarray sum ending at $r$ is $S_r - \min_{l < r} S_l$, so a running minimum is enough instead of pair enumeration. In the usual form it is two lines: cur = max(v, cur + v) and best = max(best, cur), initialized with best = cur = a[0]. Here cur is the best sum of a subarray ending at the current element, and the choice inside max decides whether to keep the left boundary or move it here. For the array $[5, -2, -6, 7, -1, 4]$, cur takes the values $5, 3, -3, 7, 6, 10$; the maximum 10 is the segment $[7, -1, 4]$, and enumerating all 21 subarrays agrees. Initializing best = 0 instead of a[0] is the main trap: on an all-negative array, that code returns zero.
Technique 3. Two pointers and the sliding window
Two-way movement. In a sorted array, find a pair with a given sum using pointers at the two ends: if the sum is too small, move the left pointer right; if it is too large, move the right pointer left. This is $O(n\log n)$ because of sorting—more expensive than a hash set, but it uses no extra hash-table memory.
Fixed-length window. The simplest case: the window length is given, both boundaries move together at every step, and the new sum is obtained from the old one in two operations—add the element arriving on the right and subtract the one leaving on the left (w1103). A full recomputation costs $O(nk)$; a shift costs $O(n)$ for any window length.
Variable-length window. Both pointers move in one direction: the right one expands the segment, and the left one catches up when the condition breaks. Find the longest subarray with sum at most 9 in $[6, 1, 2, 3, 1, 7, 2, 4]$:
a = [6, 1, 2, 3, 1, 7, 2, 4]
s = 0; left = 0; best = 0
for right, v in enumerate(a):
s += v
while s > 9: # the condition broke—move the left boundary
s -= a[left]; left += 1
best = max(best, right - left + 1)
print(best) # 4The answer is 4—the segment $[1, 2, 3, 1]$ has sum 7. Enumerating all 36 subarrays gives the same result, but the window makes one pass.
Why the window is linearEach of the two pointers traverses the array exactly once and never moves backward, so there are at most $2n$ pointer moves, however many times the inner while runs. This is also the only thing you can break: if the left boundary jumps backward, correctness and linearity disappear together.
When the window condition is about composition rather than sum (“all characters are distinct”, “no more than two different letters”), keep the state in a dictionary: a character and its last index, or its occurrence count.
Technique 4. Binary search on the answer
In a sorted array, binary search finds an element in $\log_2 n$ steps. But the exam more often uses a different twist: search for the answer number itself, not for an array element. The signal is “the minimum such that” or “the maximum such that,” plus an easy check for a particular value. Example. Find the smallest integer $x$ with $x^{2} \ge 3000$. The predicate is x * x >= 3000, and it is monotone: if $x$ works, every larger value works too. The valid values form a ray, and we need its left boundary.
lo, hi = 1, 3000 # hi is guaranteed to work
while lo < hi:
mid = (lo + hi) // 2
if mid * mid >= 3000: hi = mid # works—the boundary is no farther right than mid
else: lo = mid + 1 # fails—mid is definitely too small
print(lo) # 55 in 12 steps instead of 3000 checksCheck the neighbor: $55^{2} = 3025 \ge 3000$, while $54^{2} = 2916 < 3000$—so 55 really is the boundary.
Memorize the template exactlywhile lo < hi, with hi = mid and lo = mid + 1 inside; the answer is in lo. Invariant: hi always works and lo is the left edge of the search region; the interval strictly shrinks each step, so there is no infinite loop.
For “the maximum such that,” use the mirror template: mid = (lo + hi + 1) // 2, then lo = mid and hi = mid - 1; the answer is again in lo. With the ordinary midpoint it loops on two neighboring values—a classic trap. Two more places where a correct idea produces a wrong number: the bounds are too narrow, leaving the answer outside the interval, or the predicate is not monotone, in which case the technique does not apply at all.
Technique 5. Bitwise numbers
XOR (^) combines binary representations without carries: $1 \oplus 1 = 0$, $1 \oplus 0 = 1$, and $0 \oplus 0 = 0$. For example, $22 \oplus 13$: the representations $10110$ and $01101$ give $11011 = 27$. This yields the two identities behind every XOR problem: $x \oplus x = 0$ and $x \oplus 0 = x$; in a chain, anything that appears twice cancels itself.
The second fact concerns comparison by bits. The “Bridge” fact says that one higher bit is greater than the sum of all lower bits, so compare options starting with the most significant bit: a win there outweighs any loss across all lower bits together. This is what replaces pair enumeration with a descent through the binary-representation tree—the same halving idea as technique 4, except that candidates are split by the next bit.
That gives a rule for pairs. For the maximum XOR, at each bit from most significant to least, look for a partner with the opposite bit (b1105); for the minimum, look for one with the same bit (s1101). The minimum has another consequence of the same fact: it is always attained by a pair of neighbors in sorted order, so on small data it is enough to make $n - 1$ checks instead of checking every pair.
Hidden $O(n^{2})$ in Pythonresult += ch inside a loop does not append a character; it copies the entire string because strings are immutable, turning apparently linear code into quadratic code. Accumulate pieces in a list and use "".join(parts) at the end. This trap survives: the code passes small tests and hits the limit on large input.
What should stay in your head
- The constraint in the statement tells you the feasible complexity; $10^{12}$ operations take hours.
list gives order and indices; set and dict give instant lookup at the cost of memory; a heap gives the $k$ extremes.- Ask “was it seen earlier?” instead of “will it appear later?”: a set stores a fact, a counter stores a count.
- A segment sum is the difference of two prefixes; “divisible by $k$” means equal remainders; set
c[0] = 1. - Kadane’s algorithm asks the same question of earlier prefixes, but about a minimum rather than equality.
- A window is linear because both boundaries move only forward; its length is either fixed by a number or determined by a condition.
- “The minimum such that” plus an easy check means binary search on the answer; use
hi = mid and lo = mid + 1, then check the neighbor. - $x \oplus x = 0$; the highest bit outweighs all lower bits together: for maximum XOR use an opposite-bit partner, for minimum XOR use a same-bit partner.