Saltar al contenido

Pasos de dividir a la mitad o restar uno

Fácil#tail-recursion#bit-counting~15 min

La misión

Problema

Empieza con un entero n mayor o igual que cero. En un paso, divídelo a la mitad si es par o réstale uno si es impar. Devuelve cuántos pasos hacen falta para llegar a cero. El número puede llegar a 2 elevado a 1000, así que una solución que hace una llamada recursiva por paso superará el límite de recursión predeterminado de Python.

Ejemplos

Input:  n = 14
Output: 6
Por qué: 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0
Input:  n = 2 ** 1000
Output: 1001
Por qué: 1000 divisiones a la mitad llegan a 1, y una resta llega a 0
Input:  n = 0
Output: 0
Por qué: caso límite: ya está en cero, así que no se da ningún paso

Pistas

0 / 3

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

Restricciones

  • 0 ≤ n ≤ 2¹⁰⁰⁰

¿Lo que te frena es la idea y no el código? Llamadas de cola y bucles lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio