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

Explanation

The most straight forward solution is to go through \(0, 1, \dots, n\) and count the number of bits in each integer. We can use either the Brian Kernighan method (count how many times we do num = num & (num - 1)) or the Bit Scan method which goes through each bit position and checks if it is 0 or 1 (add 1 if (i << 1) & num) > 0 for all 32 bit positions i). We use the Brian Kernighan method as it is faster. Each bit count is appeneded to a list which is our result.

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]

Complexity

Measure	Complexity	Notes
Time	\(O(n)\)	outer loop goes 0 to n, inner loop is at most 32 iterations
Auxiliary Space	\(O(1)\)

counting_bits__bit_counting.countBits(n: int) → list[int]

Return the number of 1-bits for each integer from 0 to n.

Dynamic Programming

Explanation

Observe that the number of bits in an integer \(n\) is equal to the number of bits in the right bitshifted integer n >> 1 plus whether the last bit was 1. We can use dynamic programming to create the array counting the number of 1s in the binary representation of the numbers \(0, \dots, n\) with 0 having 0 bits as our base case.

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__dynamic_programming import countBits
>>> countBits(2)
[0, 1, 1]
>>> countBits(5)
[0, 1, 1, 2, 1, 2]
>>> countBits(0)
[0]

Complexity

Measure	Complexity	Notes
Time	\(O(n)\)	one loop to create the array
Auxiliary Space	\(O(1)\)

counting_bits__dynamic_programming.countBits(n: int) → list[int]

Return the number of 1-bits for each integer from 0 to n.