Bits ligados de cada número
A missão
Problema
Dado um número inteiro não negativo n, retorne uma lista cuja entrada no índice i é a quantidade de 1s na forma binária de i, para todo i de 0 até n, inclusivo. Tente preencher a lista inteira em uma única passada, sem percorrer os dígitos de cada número.
Exemplos
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Por quê: 0, 1, 10, 11, 100, 101 em binário
Input: n = 2
Output: [0, 1, 1]
Input: n = 0
Output: [0]
Por quê: edge case: a lista ainda guarda a entrada do próprio zero
Dicas
0 / 3
Contar os 1s de cada número do zero repete trabalho. Algum número menor que você já tratou é quase idêntico ao atual.
Deslocar um número uma posição para a direita descarta o seu dígito mais baixo e mantém todos os outros. Esse número menor já está na sua lista.
Preencha a lista de 1 em diante. A contagem de i é a contagem guardada para i deslocado uma posição à direita, mais um se o dígito mais baixo de i for 1.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- n ≥ 0
Solução
Descartar o dígito binário mais baixo de i dá i deslocado uma posição à direita, um número menor cuja contagem já é conhecida; então, a contagem de i é essa contagem guardada mais o dígito descartado. Preencher a lista em ordem crescente garante que toda leitura aponte para trás, para uma entrada já pronta. Cada entrada custa um deslocamento, um AND e uma soma. O tempo é O(n), e a lista de saída ocupa O(n) de espaço.
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]Travou na ideia, e não no código? Contando bits ligados explica isso.