Saltar al contenido

K-ésimo número que falta en una lista

Fácil#binary-search#counting~20 min

La misión

Problema

Los números de ticket se reparten desde 1 en adelante, y nums lista los que ya se usaron, en orden estrictamente creciente y todos positivos. Devuelve el k-ésimo número positivo más pequeño que no aparece en nums, donde k es al menos 1. Apunta a una solución más rápida que recorrer los números uno por uno.

Ejemplos

Input:  nums = [2, 3, 4, 7, 11], k = 5
Output: 9
Por qué: los números que faltan son 1, 5, 6, 8, 9, 10, ...
Input:  nums = [1, 2, 3, 4], k = 2
Output: 6
Por qué: no falta nada dentro de la lista, así que la respuesta está más allá de su final
Input:  nums = [], k = 4
Output: 4
Por qué: caso límite: si no se usó ninguno, el k-ésimo número que falta es el propio k

Pistas

0 / 3

Tiempo objetivo
O(log n)
Espacio objetivo
O(1)

Restricciones

  • nums is strictly increasing
  • every value in nums is positive
  • k ≥ 1

¿Lo que te frena es la idea y no el código? Búsqueda binaria lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio