Padrão 4: O poder do XOR
O XOR (
^) tem uma propriedade quase mágica que resolve uma família inteira de problemas "achar o que sobra" em O(n) tempo e O(1) espaço — sem hash map, sem ordenar.
Tente primeiro: Missing Number
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dado um array nums com n números distintos tirados de 0..n, um número está faltando. Encontre-o. Tente fazer em O(n) tempo e O(1) de espaço extra.
Exemplo: nums = [3, 0, 1] (deveria ter 0,1,2,3) → falta o 2.
Tentou? Provavelmente você usou um conjunto (set) ou a fórmula da soma — ambas funcionam! A teoria abaixo mostra uma terceira via, com XOR, que não usa memória extra nem corre risco de overflow.
A teoria: as propriedades do XOR
O XOR compara bit a bit e dá 1 onde os bits diferem. Disso saem três propriedades que, juntas, são uma ferramenta poderosa:
1. a ^ a = 0 (qualquer coisa com ela mesma se cancela)
2. a ^ 0 = a (XOR com zero não muda nada)
3. a ^ b = b ^ a (a ordem não importa — comutativo e associativo)
Junte tudo: se você fizer o XOR de uma porção de números, tudo que aparece em par se cancela (propriedade 1) e sobra exatamente o que apareceu um número ímpar de vezes. É um "detector de desemparelhados" que não guarda nada na memória.
Os sinais de XOR no enunciado
- "Todo elemento aparece duas vezes, exceto um" → o solitário sobra.
- "Um número está faltando" em uma sequência conhecida → emparelhe o que existe com o que deveria existir; o ausente sobra.
- "Troque dois valores sem variável auxiliar", "ache a diferença de bits".
- Restrição O(1) de espaço num problema que pareceria pedir um hash set.
Exemplo 1 — Missing Number
"Um array tem n números distintos de 0..n; um está faltando."
- Força bruta / hash: marque os presentes num set e veja qual falta — O(n) tempo mas O(n) espaço.
- Soma:
soma(0..n) − soma(nums)dá o ausente — O(1) espaço, mas a soma pode estourar inteiros enormes. - XOR (sem overflow, sem memória): faça o XOR de todos os índices
0..ncom todos os valores. Cada número presente aparece como índice e como valor → se cancela. O único índice sem valor correspondente é o que falta — e ele sobra.
Veja o acumulador res em binário enquanto os pares se cancelam:
Por que é O(n) tempo e O(1) espaço?
Uma única passada pelos n elementos, com um XOR (O(1)) por passo →
O(n) de tempo. O estado é uma só variável acumuladora, não importa o
tamanho da entrada → O(1) de espaço. E, diferente da soma, o XOR nunca
"cresce" além da largura do inteiro — sem risco de overflow.
| Solução | Tempo | Espaço | Observação |
|---|---|---|---|
| Hash set | O(n) | O(n) | memória extra |
| Soma de Gauss | O(n) | O(1) | pode estourar inteiros |
| XOR | O(n) | O(1) | sem overflow, sem memória |
Exemplo 2 — Single Number
"Todo elemento aparece duas vezes, menos um. Ache o solitário." É o XOR na sua forma mais pura — sem nem precisar dos índices:
Comece de 0 (propriedade 2: não atrapalha), faça XOR de tudo: cada par some,
o solitário fica. Uma linha, O(n)/O(1). Tente resolver isso com qualquer outra
abordagem em O(1) de espaço — você vai entender por que o XOR é especial.
🧠 Quiz de fixação
0/41. Quanto vale a ^ a, para qualquer a?
2. Por que fazer XOR de todos os elementos de um array onde tudo aparece em par (menos um) revela o solitário?
3. Qual vantagem o XOR tem sobre a 'soma de Gauss' no Missing Number?
4. 'Troque os valores de duas variáveis a e b sem usar uma variável auxiliar.' Que ferramenta da aula resolve?
Resumo
- XOR:
a^a=0,a^0=a, comutativo. Pares se cancelam; o desemparelhado sobra. - Single Number: XOR de tudo a partir de 0 → o solitário. O(n)/O(1).
- Missing Number: XOR de índices
0..ncom os valores → o ausente sobra, sem overflow nem memória. - Sinais: "aparece duas vezes menos um", "está faltando", O(1) de espaço.
Próxima aula: técnicas que combinam bits com outras ideias — counting bits,
reverse bits e somar sem +.