0Pricing
DSA Interview Prep · Aula

Número único e propriedades de XOR

Use a propriedade de inversão própria de XOR para encontrar o único elemento que aparece uma vez em uma lista na qual todos os demais aparecem duas vezes; depois, amplie para número único II e III.

Número único e propriedades de XOR é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.

O problema do Número Único

O problema do Número Único (LeetCode 136) propõe o seguinte: dado um vetor em que cada elemento aparece exatamente duas vezes, exceto um, encontre o elemento que aparece apenas uma vez. A restrição de tempo O(n) e espaço O(1) exclui tabelas de dispersão (espaço O(n)) e a ordenação (tempo O(n log n) ou espaço O(n) para a ordenação).

A solução elegante usa XOR. Aplique XOR a todos os elementos. Como elementos idênticos se cancelam (a ^ a = 0) e XOR é comutativo e associativo, todos os elementos que formam pares desaparecem, restando apenas o elemento único. Essa é uma das soluções O(n)/O(1) mais satisfatórias de toda a programação competitiva.

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

# All pairs cancel, leaving the lone element
print(single_number([2, 2, 1]))              # 1
print(single_number([4, 1, 2, 1, 2]))        # 4
print(single_number([1]))                    # 1
print(single_number([7, 3, 5, 3, 7]))        # 5

# Even more concise with functools.reduce
from functools import reduce
from operator import xor
print(reduce(xor, [2, 2, 1]))  # 1

Por que XOR funciona: três propriedades fundamentais

O poder do XOR vem da combinação de três propriedades algébricas:

  • Auto-inversa: a ^ a = 0 — valores idênticos se cancelam
  • Elemento neutro: a ^ 0 = a — aplicar XOR com zero não altera os valores
  • Comutatividade e associatividade: a ordem não importa, e os agrupamentos também não

Juntas, essas três propriedades fazem com que o XOR de um multiconjunto reduza a 0 todos os elementos que aparecem um número par de vezes, deixando apenas os elementos que aparecem um número ímpar de vezes. No Número Único I, exatamente um elemento aparece uma vez (um número ímpar de vezes), portanto ele é o resultado do XOR.

# Demonstrating the three XOR properties
print('Self-inverse: a ^ a = 0')
for a in [5, 13, 255, 0]:
    print(f'  {a} ^ {a} = {a ^ a}')

print('Identity: a ^ 0 = a')
for a in [5, 13, 0, 1024]:
    print(f'  {a} ^ 0 = {a ^ 0}')

print('Commutativity and Associativity:')
a, b, c = 3, 5, 7
print(f'  a^b^c = {a^b^c}')
print(f'  c^a^b = {c^a^b}')  # same result
print(f'  (a^b)^c = {(a^b)^c}')
print(f'  a^(b^c) = {a^(b^c)}')  # same result

Acompanhando o Número Único

Acompanhemos [4, 1, 2, 1, 2] passo a passo para observar o cancelamento em ação. Aplicamos XOR a todos os elementos: 4 ^ 1 ^ 2 ^ 1 ^ 2. Como XOR é comutativo, podemos reordenar a expressão como (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Os pares se cancelam e somente 4 permanece.

No algoritmo real, não reordenamos os elementos — aplicamos XOR da esquerda para a direita. Mas o resultado final é o mesmo, pois a comutatividade e a associatividade garantem que a ordem não afeta o resultado. Você pode agrupar mentalmente os pares onde quiser: todos eles se cancelarão.

nums = [4, 1, 2, 1, 2]
result = 0
print(f'Start: result = {result} ({bin(result)})')
for n in nums:
    prev = result
    result ^= n
    print(f'XOR {n:2d}: {bin(prev):8s} ^ {bin(n):6s} = {bin(result):8s} = {result}')
print(f'Final: {result}')  # 4

# Alternative: show pair cancellation
print('\nMath view:')
print('4 ^ 1 ^ 2 ^ 1 ^ 2')
print('= 4 ^ (1^1) ^ (2^2)')
print('= 4 ^  0   ^  0')
print('= 4')

Número Único II: cada elemento aparece três vezes

Número Único II (LeetCode 137): cada elemento aparece três vezes, exceto um que aparece uma vez. XOR sozinho não funciona — os pares não se cancelam quando aparecem em trios. Em vez disso, contamos quantas vezes cada bit aparece em todos os números. Se um bit aparece no elemento procurado, ele contribui com 1; nos elementos que aparecem três vezes, contribui com 3. Calcule a contagem módulo 3 de cada bit para isolar os bits do elemento procurado.

Podemos simular isso com duas variáveis inteiras, ones e twos, que atuam como um contador no nível dos bits módulo 3. Essa é uma abordagem de lógica digital: ones armazena os bits vistos um número ímpar de vezes, módulo 2, e twos armazena os bits vistos duas vezes, módulo 3.

def single_number_II(nums):
    ones, twos = 0, 0
    for n in nums:
        ones = (ones ^ n) & ~twos   # bits seen 1 mod 3 times
        twos = (twos ^ n) & ~ones   # bits seen 2 mod 3 times
    return ones  # bits seen exactly once

print(single_number_II([2, 2, 3, 2]))    # 3
print(single_number_II([0, 1, 0, 1, 0, 1, 99]))  # 99

# Simpler but O(32) bit-by-bit approach
def single_number_II_simple(nums):
    result = 0
    for bit in range(32):
        total = sum((n >> bit) & 1 for n in nums)
        if total % 3 == 1:
            result |= (1 << bit)
    return result

print(single_number_II_simple([2, 2, 3, 2]))  # 3

Número Único III: dois elementos aparecem uma vez

Número Único III (LeetCode 260): dois elementos aparecem uma vez cada; todos os demais aparecem duas vezes. Aplique XOR a todos os elementos para obter a ^ b, o XOR dos dois elementos únicos. Como a ≠ b, pelo menos um bit em a ^ b é 1 — encontre o bit 1 de menor posição de a ^ b usando diff = xor_all & (-xor_all).

Esse bit é 1 em exatamente um dos elementos, a ou b. Divida todos os números em dois grupos, de acordo com a presença desse bit. Aplique XOR separadamente a cada grupo — os elementos em pares se cancelam, restando a em um grupo e b no outro.

def single_number_III(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n              # xor_all = a ^ b

    diff = xor_all & (-xor_all)  # isolate lowest differing bit

    a = 0
    for n in nums:
        if n & diff:              # group 1: has the diff bit set
            a ^= n
    b = xor_all ^ a              # a ^ b ^ a = b
    return [a, b]

print(sorted(single_number_III([1, 2, 1, 3, 2, 5])))   # [3, 5]
print(sorted(single_number_III([-1, 0])))               # [-1, 0]
print(sorted(single_number_III([0, 1])))                # [0, 1]

Encontrando o número ausente com XOR

O problema do Número Ausente (LeetCode 268) é o seguinte: dado um vetor com n números distintos de 0 a n, encontre o número ausente. Aplique XOR a todos os números do vetor e a todos os números de 0 a n. Os pares se cancelam, deixando o número ausente. Isso resulta em tempo O(n) e espaço O(1).

Como alternativa, use a fórmula da soma aritmética: expected = n*(n+1)//2 e depois subtraia a soma real. As duas abordagens têm tempo O(n) e espaço O(1). XOR é mais robusto porque evita possíveis estouros de capacidade de inteiros em linguagens que usam inteiros de largura fixa.

def missing_number_xor(nums):
    n = len(nums)
    result = n              # start with n (the last expected value)
    for i, num in enumerate(nums):
        result ^= i ^ num   # XOR with both index and value
    return result

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

for nums, expected in [([3,0,1], 2), ([0,1], 2), ([9,6,4,2,3,5,7,0,1], 8)]:
    xor_ans = missing_number_xor(nums)
    sum_ans = missing_number_sum(nums)
    print(f'nums={nums}: XOR={xor_ans}, Sum={sum_ans}, expected={expected}')

Troca com XOR sem variável temporária

XOR permite trocar duas variáveis sem usar uma variável temporária. O truque consiste em a ^ b ^ a = b e a ^ b ^ b = a. Faça três atribuições com XOR em sequência: a ^= b, depois b ^= a e, por fim, a ^= b. Depois das três operações, a contém o valor original de b, e b contém o valor original de a.

Observação importante: esse truque falha se a e b fizerem referência à mesma posição de memória, ou seja, se forem a mesma variável. Nesse caso, a ^= a define a como 0, e o valor é perdido. Em Python, o desempacotamento de tupla (a, b = b, a) é mais seguro e claro. A troca com XOR é útil principalmente em contextos de C e sistemas embarcados, nos quais não há memória extra disponível.

# XOR swap
a, b = 17, 42
print(f'Before: a={a}, b={b}')
a ^= b   # a = 17 ^ 42
b ^= a   # b = 42 ^ (17 ^ 42) = 17
a ^= b   # a = (17 ^ 42) ^ 17 = 42
print(f'After:  a={a}, b={b}')   # a=42, b=17

# The caveat: same variable/reference => broken
c = 99
# If a and b pointed to same value:
c ^= c   # c = 0  (destroyed!)
print(f'Same-variable XOR swap: c={c}')  # 0, not 99

# Pythonic swap: always prefer this
a, b = 17, 42
a, b = b, a   # safe, clear, handles aliases
print(f'Pythonic: a={a}, b={b}')

XOR em dispersão e somas de verificação

XOR é um componente comum em somas de verificação e verificações de paridade. Aplicar XOR a todos os bytes de um bloco de dados produz uma soma de verificação de um byte. Se um único bit mudar durante a transmissão, a soma de verificação também mudará, detectando o erro. Essa abordagem é mais simples que CRC, mas detecta todos os erros de um único bit.

XOR também é usado na paridade do RAID-5: para três unidades, armazene na terceira o XOR dos dados das outras duas. Se uma unidade falhar, aplique XOR às duas unidades restantes para reconstruir os dados perdidos. Essa é exatamente a lógica do Número Único ao contrário — a unidade de paridade é o “elemento único” que codifica o que se cancela quando as três unidades passam pela operação XOR.

# Simple XOR checksum
def xor_checksum(data):
    result = 0
    for byte in data:
        result ^= byte
    return result

data = [0x48, 0x65, 0x6C, 0x6C, 0x6F]  # 'Hello' in ASCII
checksum = xor_checksum(data)
print(f'Checksum: {hex(checksum)}')

# Detect corruption
corrupted = data[:]
corrupted[2] ^= 0xFF   # flip all bits of 3rd byte
new_checksum = xor_checksum(corrupted)
print(f'Original checksum: {hex(checksum)}')
print(f'Corrupted checksum: {hex(new_checksum)}')
print(f'Error detected: {checksum != new_checksum}')

# RAID-5 parity recovery
d1 = [1, 0, 1, 1]
d2 = [0, 1, 1, 0]
parity = [d1[i] ^ d2[i] for i in range(4)]
recovered = [parity[i] ^ d2[i] for i in range(4)]  # recover d1
print(f'd1={d1}, parity={parity}, recovered={recovered}')

XOR e problemas de subconjuntos

XOR aparece em problemas de subconjuntos quando é necessário calcular o XOR de todos os subconjuntos. Uma observação importante: para n elementos, cada elemento aparece exatamente em 2^(n-1) subconjuntos. Se n > 1, cada elemento aparece em um número par de subconjuntos, portanto sua contribuição para o XOR se cancela. O XOR de todos os resultados de XOR dos subconjuntos é 0 quando n > 1.

Para n == 1, o único subconjunto não vazio é o próprio elemento, portanto o XOR de todos os subconjuntos é esse elemento. Esse tipo de raciocínio — usando propriedades do XOR e contagem — é avaliado em problemas avançados de manipulação de bits.

from itertools import combinations
from functools import reduce
from operator import xor

def xor_of_all_subsets(arr):
    n = len(arr)
    total_xor = 0
    for r in range(1, n + 1):
        for subset in combinations(arr, r):
            subset_xor = reduce(xor, subset)
            total_xor ^= subset_xor
    return total_xor

# For n > 1, each element appears 2^(n-1) times (even) => cancels
# Result is always 0 for n > 1
for arr in [[1,2,3], [5,7], [1], [1,2,3,4]]:
    result = xor_of_all_subsets(arr)
    predicted = arr[0] if len(arr) == 1 else 0
    print(f'arr={arr}: XOR of all subsets = {result}, predicted = {predicted}')

Padrão de entrevista: XOR para encontrar elementos únicos

Reconheça o padrão de XOR para encontrar elementos únicos quando um problema afirma: “cada elemento aparece k vezes, exceto um que aparece m vezes, onde m mod k != 0”. Para k=2, m=1 (Número Único I): aplique XOR a todos os elementos. Para k=3, m=1 (Número Único II): conte os bits módulo 3. Para k=2, m=1 com dois elementos únicos (Número Único III): aplique XOR e depois divida pelo bit diferente de menor posição.

A abordagem geral para um k arbitrário é contar o total de ocorrências de cada bit e calcular o módulo k. Se a contagem for diferente de zero, esse bit pertence ao elemento único. Isso produz um algoritmo O(32n) = O(n), com espaço O(1), para qualquer k.

def single_number_k_times(nums, k):
    '''Find the element that appears m times when all others appear k times.'''
    # Count each bit's occurrence and take mod k
    result = 0
    for bit in range(32):
        total = sum((n >> bit) & 1 for n in nums)
        if total % k != 0:
            result |= (1 << bit)
    # Handle negative 32-bit numbers
    if result >= (1 << 31):
        result -= (1 << 32)
    return result

# k=2, element appears once
print(single_number_k_times([2,2,1], 2))         # 1
# k=3, element appears once
print(single_number_k_times([2,2,3,2], 3))       # 3
# k=4, element appears once
print(single_number_k_times([1,1,1,1,7,2,2,2,2], 4))  # 7

Problemas comuns de entrevista sobre XOR

Além da família do Número Único, XOR aparece nestes problemas frequentes em entrevistas:

  • Encontrar a diferença (LC 389): aplique XOR a todos os caracteres das duas cadeias de caracteres; o caractere extra permanece
  • Distância de Hamming (LC 461): aplique XOR a dois números e conte os bits 1 no resultado
  • Distância de Hamming total (LC 477): conte os 0s e 1s em cada posição de bit entre todos os pares
  • Consultas de XOR em um subvetor (LC 1310): use um vetor de XOR acumulado para consultas de intervalos

Em cada caso, a propriedade de cancelamento do XOR elimina a redundância e reduz uma abordagem de força bruta O(n²) a O(n).

# Find the difference between two strings
def find_the_difference(s, t):
    result = 0
    for c in s + t:
        result ^= ord(c)
    return chr(result)

print(find_the_difference('abcd', 'abcde'))  # 'e'

# Hamming distance: count differing bits
def hamming_distance(x, y):
    diff = x ^ y
    count = 0
    while diff:
        count += diff & 1
        diff >>= 1
    return count
    # or: bin(x ^ y).count('1')

print(hamming_distance(1, 4))   # 2: 001 vs 100 differ in bits 0 and 2
print(hamming_distance(3, 1))   # 1: 011 vs 001 differ in bit 1

# Prefix XOR for range queries
def xor_queries(arr, queries):
    prefix = [0] * (len(arr) + 1)
    for i, v in enumerate(arr):
        prefix[i+1] = prefix[i] ^ v
    return [prefix[r+1] ^ prefix[l] for l, r in queries]

print(xor_queries([1,3,4,8], [[0,1],[1,2],[0,3],[3,3]]))

Verificação rápida

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.

Recapitulação da lição

Nesta lição, você aprendeu que a propriedade auto-inversa do XOR (a ^ a = 0) faz com que elementos em pares se cancelem, deixando apenas o elemento único quando aplicamos XOR a todos os números, que o Número Único II usa a contagem de bits módulo 3, enquanto o Número Único III divide os elementos pelo bit diferente de menor posição e que XOR também resolve problemas de número ausente, encontrar a diferença, distância de Hamming e consultas de XOR em intervalos. Em seguida, exploraremos máscaras de bits para definir, limpar, alternar e verificar bits individuais.

Perguntas Frequentes

A aula “Número único e propriedades de XOR” é grátis?

Sim — o texto completo de “Número único e propriedades de XOR” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.

O que vou aprender em “Número único e propriedades de XOR”?

Use a propriedade de inversão própria de XOR para encontrar o único elemento que aparece uma vez em uma lista na qual todos os demais aparecem duas vezes; depois, amplie para número único II e III. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar DSA Interview Prep?

Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.

Quanto tempo leva a aula “Número único e propriedades de XOR”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de DSA Interview Prep?

Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos
  2. Número único e propriedades de XOR
  3. Máscaras de bits: definir, limpar, alternar e verificar
  4. Contagem de bits, número ausente e inversão de bits
← Voltar para DSA Interview Prep