Counting Bits

Problem

https://leetcode.com/problems/counting-bits/

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1‘s in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

0 <= n <= 10⁵

Pattern

Bit Manipulation, Dynamic Programming

Approaches

Bit Counting

Code

def countBits(n: int) -> list[int]:
    """Return the number of 1-bits for each integer from 0 to *n*."""
    result = []
    for i in range(n + 1):
        bits = 0
        num = i
        while num > 0:
            num = num & (num - 1)
            bits += 1
        result.append(bits)
    return result

Test

>>> from counting_bits__bit_counting import countBits
>>> countBits(2)
[0, 1, 1]
>>> countBits(5)
[0, 1, 1, 2, 1, 2]
>>> countBits(0)
[0]

counting_bits__bit_counting.countBits(n: int) → list[int]: Return the number of 1-bits for each integer from 0 to n.

DP

Code

def countBits(n: int) -> list[int]:
    """Return the number of 1-bits for each integer from 0 to *n*."""
    bits = [0] * (n + 1)
    for i in range(n + 1):
        bits[i] = bits[i >> 1] + (1 & i)
    return bits

Test

>>> from counting_bits__dp import countBits
>>> countBits(2)
[0, 1, 1]
>>> countBits(5)
[0, 1, 1, 2, 1, 2]
>>> countBits(0)
[0]

counting_bits__dp.countBits(n: int) → list[int]: Return the number of 1-bits for each integer from 0 to n.