Problema
La lista contiene n números distintos tomados de 0, 1, …, n, por lo que falta exactamente un número en ese rango. Encuéntralo. (Pista: compara el total esperado con el total real.)
Implementa missing_number(numbers).
Entrada
numbers: n números distintos del 0 al n.
Salida
Devuelve el número que falta.
Restricciones
0 ≤ n ≤ 100,000
Ejemplos
Entrada:
numbers = [3, 0, 1]
Salida esperada:
expected = 2Entrada:
std::vector<long long> numbers = {3, 0, 1};
Salida esperada:
long long expected = 2;Entrada:
long[] numbers = new long[] {3, 0, 1};
Salida esperada:
long expected = 2;Explicación
n = 3, así que el rango es 0–3; falta el 2.
Entrada:
numbers = [0]
Salida esperada:
expected = 1Entrada:
std::vector<long long> numbers = {0};
Salida esperada:
long long expected = 1;Entrada:
long[] numbers = new long[] {0};
Salida esperada:
long expected = 1;Explicación
n = 1 y el rango es 0–1; falta el 1.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Los números deben cubrir todo el rango de 0 a n excepto por un hueco.
Pista 2
Compara lo que sumaría el rango completo con lo que realmente suma la lista.
Pista 3
Cuidado con el caso en que el valor faltante sea 0 o n.
Complejidad esperada
tiempo O(n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.