Saltar al contenido

El valor que falta

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

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

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

¿Lo que te frena es la idea y no el código? Trucos con XOR lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio