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 la cantidad. Para n = 2^31 - 1 , son 61 pasos. Contar los dígitos binarios con instrucciones de bits integradas es O(1) .

Q: ¿Cuál es la fórmula para el número de pasos?

Para n > 0 , la respuesta es la longitud de n en binario, menos uno, más el número de bits 1. Cada bit 1 cuesta una resta y cada dígito después del uno inicial cuesta una división entre dos. Para n = 0 , la respuesta es 0 .

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

2^31 - 1 , que en binario es treinta y un unos. Necesita 31 restas y 30 divisiones entre dos, 61 pasos en total. Ningún número menor tiene tantos dígitos y tantos unos 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 cuenta como 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 sigue la secuencia 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 divide por 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 1 inicial cuestan seis divisiones entre dos, 12 pasos.

+12 pruebas ocultas al enviar

Para ir más allá

Supón que un número impar también puede aumentar en 1 en lugar de disminuir. ¿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

Ejecutar la regla ya es rápido: cada división por la mitad reduce el número a la mitad, así que incluso 2^31 - 1 solo necesita 61 pasos. Lo interesante es ver qué hace la regla con los dígitos binarios. 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 la respuesta es el número de dígitos más el número de unos, menos uno.

Ejecuta el proceso

Intuición

Haz lo que indica la instrucción. Mientras n sea mayor que 0, divídelo por la mitad si es par, réstale 1 si es impar y cuenta el paso. Para 14, el bucle visita 7, 6, 3, 2, 1 y 0: seis pasos.

El bucle es corto porque una resta siempre hace que un número impar sea par, así que al menos cada dos pasos se divide por la mitad. Un número menor que 2^31 se divide por la mitad como máximo 30 veces antes de llegar a 1 y, con una resta antes de cada división por la mitad y otra al final, el bucle se ejecuta como máximo 61 veces.

La entrada 0 no necesita ningún caso especial: la condición del bucle falla de inmediato 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

Observa el proceso en binario. 14 es 1110. Dividir por la mitad elimina el último dígito: 111. Restar 1 a un número impar borra su último dígito, un 1: 110. Así que cada paso elimina el último dígito o convierte un 1 final en un 0.

Ahora, cuenta. Hay que borrar cada 1 del número una vez, lo que cuesta una resta por cada 1. Hay que eliminar cada dígito, lo que cuesta una división por la mitad por cada dígito, excepto el primero: cuando solo queda 1, la resta que lo borra ya da 0. Así que la respuesta es length - 1 + ones. Para 14 = 1110, eso es 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust y Swift tienen funciones integradas para ambos recuentos (el recuento de ceros iniciales y el recuento de bits a uno), que se compilan en instrucciones únicas en la mayoría de los procesadores. En los demás lenguajes se escribe n en binario y se cuentan los caracteres, o se leen los dígitos con % 2; eso es un bucle de como máximo 31 iteraciones. Devuelve 0 primero para n = 0: no tiene ningún bit 1 que sirva de referencia 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

La regla tiene dos líneas. Los errores están en los casos límite y en el desfase de uno de la fórmula.

Olvidar n = 0 en la fórmula de bits. Sin dígitos ni unos, 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 entre dos 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.
Combinar dos pasos en uno. Escribir n = (n-1) / 2 para un número impar realiza una resta y una división entre dos a la vez, así que debe sumar 2 al recuento, no 1. De lo contrario, 14 da 4 en lugar de 6.
Usar un bucle mientras n > 1. Eso se detiene un paso antes, porque el último paso convierte 1 en 0. El bucle debe ejecutarse hasta que n sea 0.

Preguntas frecuentes4

¿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 la cantidad. Para n = 2^31 - 1, son 61 pasos. Contar los dígitos binarios con instrucciones de bits integradas es O(1).

¿Cuál es la fórmula para el número de pasos?

Para n > 0, la respuesta es la longitud de n en binario, menos uno, más el número de bits 1. Cada bit 1 cuesta una resta y cada dígito después del uno inicial cuesta una división entre dos. Para n = 0, la respuesta es 0.

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

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

¿Por qué dividir entre dos 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 en uno cada potencia, lo que desplaza cada dígito un lugar a la derecha y elimina el 0 final. Eso es exactamente lo que hace n >> 1, así que puedes escribir la operación de división por dos de cualquiera de las dos formas.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

n = 14

Esperado