Counting Bits

# 問題

0以上num以下の数字を2進数で表記したときの，ビット1の個数を計算し，長さnums + 1の配列にして返せ．

# 答え

iを2進数表記したときの1の個数をf[i]とすると，

f[i] = f[i // 2] + i % 2

が成立する．

1
2
3
4
5
6
7
def solve(num):
    table = [0 for _ in range(num + 1)]
    for i in range(1, num + 1):
        table[i] = table[i >> 1] + (i & 1)
    return table

print(solve(5)) # => [0, 1, 1, 2, 1, 2]

pythonの標準の便利関数を使うと簡単だけどこれは求められていなさそう．

1
2
3
4
def solve(num):
    return [bin(i).count('1') for i in range(num + 1)]

print(solve(5)) # => [0, 1, 1, 2, 1, 2]