Single Number y propiedades de XOR
Use la propiedad de inverso propio de XOR para encontrar el único elemento que aparece una vez en una lista donde todos los demás aparecen dos veces, y extienda el método a single-number-II y III.
Single Number y propiedades de XOR es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El problema Single Number
El problema Single Number (LeetCode 136) plantea lo siguiente: dado un array en el que cada elemento aparece exactamente dos veces salvo uno, encuentre el elemento que aparece una sola vez. La restricción de tiempo O(n) y espacio O(1) descarta los mapas hash (espacio O(n)) y la ordenación (tiempo O(n log n) o espacio O(n) para la ordenación).
La solución elegante utiliza XOR. Aplique XOR a todos los elementos. Como los elementos idénticos se cancelan (a ^ a = 0) y XOR es conmutativo y asociativo, todos los elementos emparejados desaparecen y solo queda el elemento único. Esta es una de las soluciones O(n)/O(1) más satisfactorias de toda la programación 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])) # 1Por qué funciona XOR: tres propiedades clave
La potencia de XOR proviene de la combinación de tres propiedades algebraicas:
- Inverso de sí mismo:
a ^ a = 0— los valores idénticos se cancelan entre sí - Elemento neutro:
a ^ 0 = a— aplicar XOR con cero no modifica los valores - Conmutatividad y asociatividad: el orden no importa y las agrupaciones tampoco
Estas tres propiedades juntas hacen que aplicar XOR a un multiconjunto reduzca a 0 todos los elementos que aparecen un número par de veces, dejando solo los elementos que aparecen un número impar de veces. En Single Number I, exactamente un elemento aparece una vez (un número impar de veces), por lo que ese es el resultado de 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 resultRecorrido de Single Number
Sigamos [4, 1, 2, 1, 2] paso a paso para observar la cancelación en acción. Aplicamos XOR a todos los elementos: 4 ^ 1 ^ 2 ^ 1 ^ 2. Como XOR es conmutativo, podemos reordenarlo así: (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Los pares se cancelan y solo queda 4.
En el algoritmo real, no reordenamos los elementos: aplicamos XOR de izquierda a derecha. Sin embargo, el resultado final es el mismo porque la conmutatividad y la asociatividad garantizan que el orden no afecta al resultado. Puede agrupar mentalmente los pares donde quiera: todos se cancelarán.
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')Single Number II: cada elemento aparece tres veces
Single Number II (LeetCode 137): cada elemento aparece tres veces salvo uno que aparece una sola vez. XOR por sí solo no funciona, porque los pares ya no se cancelan cuando aparecen tres veces. En su lugar, contamos cuántas veces aparece cada bit en todos los números. Si un bit aparece en el elemento objetivo, contribuye con 1; en los elementos que aparecen tres veces, contribuye con 3. Aplique count mod 3 a cada bit para aislar los bits del elemento objetivo.
Podemos simular esto con dos variables enteras, ones y twos, que actúan como un contador a nivel de bit módulo 3. Este es un enfoque basado en lógica digital: ones contiene los bits vistos un número impar de veces módulo 2, y twos contiene los bits vistos dos veces 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])) # 3Single Number III: dos elementos aparecen una sola vez
Single Number III (LeetCode 260): dos elementos aparecen una sola vez cada uno; todos los demás aparecen dos veces. Aplique XOR a todos los elementos para obtener a ^ b (el XOR de los dos elementos únicos). Como a ≠ b, al menos un bit de a ^ b vale 1; encuentre el bit menos significativo establecido de a ^ b mediante diff = xor_all & (-xor_all).
Este bit vale 1 exactamente en uno de a o b. Divida todos los números en dos grupos según si ese bit está establecido. Aplique XOR por separado a cada grupo: los elementos emparejados se cancelan, y quedan a en un grupo y b en el otro.
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]Encontrar el número que falta con XOR
El problema Missing Number (LeetCode 268) plantea lo siguiente: dado un array de n números distintos del 0 al n, encuentre el que falta. Aplique XOR a todos los números del array y a todos los números del 0 al n. Los pares se cancelan y queda el número que falta. Esto proporciona un tiempo O(n) y un espacio O(1).
Como alternativa, utilice la fórmula de la suma aritmética: expected = n*(n+1)//2, y reste después la suma real. Ambos enfoques son O(n)/O(1). XOR es más robusto porque evita un posible desbordamiento de enteros en lenguajes con enteros de ancho fijo.
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}')Intercambiar con XOR sin una variable temporal
XOR permite intercambiar dos variables sin utilizar una variable temporal. El truco consiste en que a ^ b ^ a = b y a ^ b ^ b = a. Aplique tres asignaciones con XOR en secuencia: a ^= b, después b ^= a y, por último, a ^= b. Después de las tres, a contiene el valor original de b y b contiene el valor original de a.
Advertencia importante: este truco falla si a y b hacen referencia a la misma ubicación de memoria (es decir, si son la misma variable). En ese caso, a ^= a asigna 0 a a y el valor se pierde. En Python, la asignación mediante desempaquetado de tuplas (a, b = b, a) es más segura y clara. El intercambio con XOR resulta principalmente útil en contextos de C o sistemas embebidos en los que no se dispone de memoria adicional.
# 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 en hashing y sumas de comprobación
XOR es un componente habitual de las sumas de comprobación y las comprobaciones de paridad. Aplicar XOR a todos los bytes de un bloque de datos produce una suma de comprobación de un solo byte. Si un solo bit cambia durante la transmisión, la suma de comprobación cambia y detecta el error. Es más sencillo que CRC, pero detecta todos los errores de un solo bit.
XOR también se utiliza en la paridad de RAID-5: para tres unidades, almacene en la tercera el XOR de los datos de las otras dos. Si una unidad falla, aplique XOR a las dos restantes para reconstruir los datos perdidos. Esta es exactamente la lógica de Single Number a la inversa: la unidad de paridad es el «elemento único» que codifica qué se cancela al aplicar XOR a las tres unidades.
# 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 y problemas de subconjuntos
XOR aparece en problemas de subconjuntos cuando necesita calcular el XOR de todos los subconjuntos. Una idea clave es que, para n elementos, cada elemento aparece exactamente en 2^(n-1) subconjuntos. Si n > 1, cada elemento aparece un número par de veces, por lo que su contribución de XOR se cancela. El XOR de todos los XOR de subconjuntos es 0 cuando n > 1.
Para n == 1, el único subconjunto no vacío es el propio elemento, por lo que el XOR de todos los subconjuntos es ese elemento. Este tipo de razonamiento, basado en las propiedades de XOR y en el recuento, se evalúa en problemas avanzados de manipulación 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}')Patrón de entrevista: XOR para encontrar elementos únicos
Reconozca el patrón de XOR para encontrar elementos únicos cuando un problema indique: «cada elemento aparece k veces salvo uno que aparece m veces, donde m mod k != 0». Para k=2, m=1 (Single Number I), aplique XOR a todos los elementos. Para k=3, m=1 (Single Number II), cuente los bits módulo 3. Para k=2, m=1 con dos elementos únicos (Single Number III), aplique XOR y después divida por el bit diferente menos significativo.
El enfoque general para cualquier k consiste en contar las apariciones totales de cada bit y calcular el módulo k. Si el recuento no es cero, ese bit pertenece al elemento único. Esto proporciona un algoritmo O(32n) = O(n) con espacio O(1) para cualquier 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)) # 7Problemas habituales de entrevistas sobre XOR
Además de la familia Single Number, XOR aparece en estos problemas frecuentes:
- Find the Difference (LC 389): aplique XOR a todos los caracteres de ambas cadenas; queda el carácter adicional
- Hamming Distance (LC 461): aplique XOR a dos números y cuente los bits 1 del resultado
- Total Hamming Distance (LC 477): cuente los 0 y los 1 en cada posición de bit entre todos los pares
- XOR Queries of a Subarray (LC 1310): utilice un array de XOR de prefijos para las consultas de rangos
En cada caso, la propiedad de cancelación de XOR elimina la redundancia y reduce una fuerza 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]]))Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: la propiedad de XOR de ser su propio inverso (a ^ a = 0) hace que los elementos emparejados se cancelen, dejando solo el elemento único al aplicar XOR a todos los números; Single Number II utiliza el recuento de bits módulo 3, mientras que Single Number III divide los elementos según el bit diferente menos significativo; y XOR también resuelve los problemas del número que falta, encontrar la diferencia, la distancia de Hamming y las consultas de XOR sobre rangos. A continuación, exploraremos las máscaras de bits para establecer, borrar, alternar y comprobar bits individuales.
Preguntas frecuentes
¿La lección «Single Number y propiedades de XOR» es gratis?
Sí — el texto completo de «Single Number y propiedades de XOR» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Single Number y propiedades de XOR»?
Use la propiedad de inverso propio de XOR para encontrar el único elemento que aparece una vez en una lista donde todos los demás aparecen dos veces, y extienda el método a single-number-II y III. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Single Number y propiedades de XOR»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Operadores bit a bit: AND, OR, XOR, NOT y desplazamientos
- Single Number y propiedades de XOR
- Máscaras de bits: establecer, borrar, alternar y comprobar
- Contar bits, número ausente e invertir bits