El valor que falta
La misión
Problema
Una lista contiene n valores distintos tomados de 0 a n, en cualquier orden, así que falta exactamente un valor de ese rango. Encuéntralo en una sola pasada y con espacio extra constante, lo que descarta ordenar y también descarta un conjunto con todo lo visto.
Ejemplos
Input: nums = [3, 0, 1]
Output: 2
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Input: nums = [0]
Output: 1
Por qué: caso límite: el valor que falta puede ser el propio n
Pistas
0 / 3
Cada posición de la lista tiene un índice, y esos índices cubren casi el mismo rango que los propios valores.
Empareja cada índice con el valor que está en él. Solo un miembro del rango completo se queda sin pareja, y necesitas una operación en la que un par emparejado desaparezca.
Combina con XOR todos los índices y todos los valores, y agrega n a la mezcla como el único índice que no existe. Cada valor presente se cancela con su número correspondiente, y el que sobrevive es el valor que nunca estuvo.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- n distinct values drawn from 0 to n
- exactly one value of the range is missing
Solución
Los índices de 0 a n-1 más el valor extra n cubren el mismo rango que cubriría la lista completa, así que combinar índices y valores con XOR empareja y cancela casi todo. Un valor se cancela con el número igual que aporta el lado de los índices, y solo queda el número que nadie aportó. Empezar el acumulador en n es lo que aporta el único índice que la lista no tiene. El tiempo es O(n) en una sola pasada y el espacio es O(1).
def missing(nums):
answer = len(nums) # n, the index the list does not have
for i, v in enumerate(nums):
answer ^= i ^ v # each matched pair cancels itself out
return answer
print(missing([3, 0, 1])) # -> 2
print(missing([9, 6, 4, 2, 3, 5, 7, 0, 1])) # -> 8
print(missing([0])) # -> 1
print(missing([1])) # -> 0¿Lo que te frena es la idea y no el código? Trucos con XOR lo explica.