Steps to Reduce a Number to Zero

Q: ¿Cuál es la complejidad temporal de reducir un número a cero?

La ejecución del proceso tarda O(log n) , porque al menos cada dos pasos se reduce a la mitad el número: 61 pasos para n = 2^31 - 1 . Contar los dígitos binarios con instrucciones de bits integradas es O(1) .

Q: ¿Qué número menor que 2^31 requiere más pasos?

2^31 - 1 , que en binario son treinta y un 1. Necesita 31 restas y 30 divisiones por dos, 61 pasos en total. Ningún número menor tiene tantos dígitos y tantos 1 a la vez.

PrincipianteManipulación de bits Matemáticas y simulación

+10

Empieza con un entero no negativo n y repite una regla hasta que llegue a 0: si el número es par, divídelo entre 2; si es impar, réstale 1. Cada aplicación de la regla es un paso. Devuelve el número de pasos que se necesitan.

Función

numberOfSteps(n: integer) → integer

ninteger: el número inicial
Devuelveinteger: el número de pasos hasta que el número llegue a 0

Restricciones

0 ≤ n ≤ 2³¹ - 1

Ejemplos

Entrada: n = 14
Salida: 6
Explicación: El número pasa por 14 → 7 → 6 → 3 → 2 → 1 → 0: tres divisiones por la mitad y tres restas, 6 pasos.

Entrada: n = 8
Salida: 4
Explicación: 8 → 4 → 2 → 1 → 0. Una potencia de dos se reduce a la mitad tres veces y necesita una resta al final: 4 pasos.

Entrada: n = 123
Salida: 12
Explicación: 123 es 1111011 en binario: siete dígitos y seis 1. Los seis 1 cuestan seis restas y los seis dígitos debajo del uno inicial cuestan seis divisiones entre dos: 12 pasos.

Para ir más allá

Supón que un número impar también puede aumentar en 1. ¿Cuál es el menor número de pasos para llegar a 0 y qué opción es correcta para 15?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

En binario, dividir por la mitad elimina el último dígito, y restar 1 a un número impar convierte su último 1 en un 0. Así que, para n > 0, la respuesta es el número de dígitos binarios más el número de unos, menos uno. Aplicar la regla directamente también es rápido: como máximo 61 pasos.

Ejecuta el proceso

Intuición

Aplica la regla y cuenta los pasos. Para 14, el bucle visita 7, 6, 3, 2, 1 y 0: seis pasos.

Una resta siempre convierte un número impar en par, así que al menos uno de cada dos pasos es una división entre dos. Un número menor que 2^31 se divide entre dos como máximo 30 veces antes de llegar a 1. Con una resta antes de cada división entre dos y una al final, el bucle se ejecuta como máximo 61 veces. Para n = 0, el bucle nunca se ejecuta y la respuesta es 0.

Algoritmo

Establece steps en 0.
Mientras n > 0: si n es par, establece n en n / 2; de lo contrario, en n-1.
Suma 1 a steps cada vez.
Devuelve steps.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

Cuenta los dígitos binarios

Intuición

Cada paso elimina el último dígito binario o convierte un 1 final en 0. 14 es 1110: al dividirlo por la mitad se obtiene 111, y al restar de 111 se obtiene 110. Cada 1 debe eliminarse una vez, lo que cuesta una resta por cada 1. Cada dígito debe eliminarse, una división por la mitad cada vez, excepto el uno inicial: cuando solo queda 1, su resta ya da 0. Así que la respuesta es length - 1 + ones, y para 14 eso es 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust y Swift tienen funciones integradas para ambos recuentos (ceros iniciales y bits activados) que se compilan en instrucciones únicas en la mayoría de los procesadores. Otros lenguajes leen los dígitos con % 2 en un bucle de como máximo 31 rondas. Primero, gestiona n = 0: no tiene ningún bit 1 que sirva de ancla para la fórmula.

Algoritmo

Si n == 0, devuelve 0.
Encuentra length, el número de dígitos binarios de n.
Encuentra ones, el número de bits 1.
Devuelve length - 1 + ones.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

Errores comunes y casos límite

Olvidar n = 0 en la fórmula de bits. length - 1 + ones da -1, y el recuento de ceros iniciales de 0 puede no estar definido (__builtin_clz(0) en C).
Contar una división por la mitad para el dígito inicial. 1 se convierte en 0 mediante una resta, así que 8 = 1000 requiere 4 - 1 + 1 = 4 pasos, no 5.
Escribir n = (n-1) / 2 para un número impar y contar un paso. Esa línea realiza dos pasos, así que el resultado para 14 es 4 en lugar de 6.
Repetir el ciclo mientras n > 1. Eso se detiene antes del último paso, que convierte 1 en 0.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de reducir un número a cero?

La ejecución del proceso tarda O(log n), porque al menos cada dos pasos se reduce a la mitad el número: 61 pasos para n = 2^31 - 1. Contar los dígitos binarios con instrucciones de bits integradas es O(1).

¿Qué número menor que 2^31 requiere más pasos?

2^31 - 1, que en binario son treinta y un 1. Necesita 31 restas y 30 divisiones por dos, 61 pasos en total. Ningún número menor tiene tantos dígitos y tantos 1 a la vez.

¿Por qué dividir por la mitad es lo mismo que desplazar a la derecha?

Un número binario es una suma de potencias de dos. Dividir un número par entre 2 reduce cada potencia en uno, lo que desplaza cada dígito un lugar a la derecha y elimina el 0 final. Eso es lo que hace n >> 1, así que puedes escribir la división entre dos de cualquiera de las dos formas.

def numberOfSteps(n):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

n = 14

Salida Esperada