O valor que falta
A missão
Problema
Uma lista guarda n valores distintos tirados de 0 até n, em qualquer ordem, então exatamente um valor desse intervalo está ausente. Encontre-o em uma única passada usando espaço extra constante, o que descarta ordenar e descarta um conjunto (set) com tudo o que já foi visto.
Exemplos
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ê: edge case: o valor que falta pode ser o próprio n
Dicas
0 / 3
Toda posição da lista tem um índice, e esses índices cobrem quase o mesmo intervalo que os próprios valores.
Forme um par entre cada índice e o valor que está nele. Só um membro do intervalo completo fica sem parceiro, e você precisa de uma operação em que um par correspondente desaparece.
Faça o XOR de todos os índices e de todos os valores juntos e coloque n na mistura como o único índice que não existe. Cada valor presente se cancela com o número correspondente, e o que sobra é o valor que nunca esteve lá.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- n distinct values drawn from 0 to n
- exactly one value of the range is missing
Solução
Os índices de 0 a n-1, mais o valor extra n, cobrem o mesmo intervalo que a lista completa cobriria; então, combinar índices e valores com XOR elimina quase tudo em pares. Um valor se cancela com o número igual vindo do lado dos índices, e sobra só o número que ninguém forneceu. Começar o acumulador em n é o que fornece o único índice que a lista não tem. O tempo é O(n), em uma única passada, e o espaço é 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])) # -> 0Travou na ideia, e não no código? Truques com XOR explica isso.