Pular para o conteúdo

Bits ligados de cada número

Fácil#bit-shifting#reuse-smaller-answer~20 min

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

Tempo-alvo
O(n)
Espaço-alvo
O(n)

Restrições

  • n ≥ 0

Travou na ideia, e não no código? Contando bits ligados explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado