Pular para o conteúdo

O valor que falta

Fácil#xor-cancel#single-pass~20 min

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

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

Travou na ideia, e não no código? Truques com XOR explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado