Pasos de dividir a la mitad o restar uno
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
La respuesta recursiva natural es uno más la respuesta para el siguiente número. Cuenta qué tan profunda se vuelve la pila de llamadas con la entrada más grande.
Reescribe la recursión para que el contador de pasos viaje como un argumento extra. Ahora la llamada recursiva es lo último que hace la función.
Una llamada que es la última acción se puede reemplazar reasignando los argumentos y volviendo al principio: un bucle que actualiza n y el contador hasta que n es cero.
- Tiempo objetivo
- O(log n)
- Espacio objetivo
- O(1)
Restricciones
- 0 ≤ n ≤ 2¹⁰⁰⁰
Solución
Con un acumulador, la recursión se vuelve una llamada de cola: la respuesta para n es la respuesta para el siguiente número con el contador aumentado en uno, y no queda nada por hacer cuando la llamada termina. Python no elimina las llamadas de cola, así que la llamada se convierte en un bucle que reasigna n y el contador, y la pila nunca crece. El conteo también tiene una forma cerrada para n mayor que cero: un paso por cada dígito binario después del primero, más uno por cada bit encendido. El tiempo es O(log n) pasos y el espacio es O(1) además del propio número.
def steps_to_zero(n):
# tail-recursive shape: steps(n, done) = done if n == 0 else steps(next n, done + 1)
done = 0
while n: # the tail call, as a loop
n = n // 2 if n % 2 == 0 else n - 1
done += 1
return done
print(steps_to_zero(14)) # -> 6
print(steps_to_zero(2 ** 1000)) # -> 1001
print(steps_to_zero(0)) # -> 0¿Lo que te frena es la idea y no el código? Llamadas de cola y bucles lo explica.