Bits encendidos de cada número
La misión
Problema
Dado un entero no negativo n, devuelve una lista cuya entrada en el índice i sea la cantidad de unos en la forma binaria de i, para cada i de 0 a n inclusive. Intenta llenar toda la lista en una sola pasada sin recorrer los dígitos de cada número.
Ejemplos
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Por qué: 0, 1, 10, 11, 100, 101 en binario
Input: n = 2
Output: [0, 1, 1]
Input: n = 0
Output: [0]
Por qué: caso límite: la lista sigue teniendo la entrada del propio cero
Pistas
0 / 3
Contar desde cero los unos de cada número repite trabajo. Algún número más pequeño que ya procesaste se parece casi exactamente al actual.
Desplazar un número una posición a la derecha elimina su dígito más bajo y conserva todos los demás. Ese número más pequeño ya está en tu lista.
Llena la lista de 1 en adelante. El conteo de i es el conteo guardado para i desplazado una posición a la derecha, más uno si el dígito más bajo de i es un uno.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- n ≥ 0
Solución
Quitar el dígito binario más bajo de i da i desplazado una posición a la derecha, un número más pequeño cuyo conteo ya se conoce, así que el conteo de i es ese conteo guardado más el dígito quitado. Llenar la lista en orden creciente garantiza que cada consulta apunte hacia atrás, a una entrada ya terminada. Cada entrada cuesta un desplazamiento, un AND y una suma. El tiempo es O(n) y la lista de salida ocupa O(n) de espacio.
def set_bits_up_to(n):
counts = [0] * (n + 1)
for i in range(1, n + 1):
counts[i] = counts[i >> 1] + (i & 1) # reuse the answer without the low digit
return counts
print(set_bits_up_to(5)) # -> [0, 1, 1, 2, 1, 2]
print(set_bits_up_to(2)) # -> [0, 1, 1]
print(set_bits_up_to(0)) # -> [0]¿Lo que te frena es la idea y no el código? Contar bits encendidos lo explica.