Counting Bits

Problem

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^5

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Solution

Approach 1: Dynamic Programming (i & (i-1))

The key insight is that i & (i-1) drops the rightmost set bit, so count[i] = count[i & (i-1)] + 1.

Implementation

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            # i & (i-1) removes rightmost set bit
            ans[i] = ans[i & (i - 1)] + 1
        return ans

Approach 2: Dynamic Programming (i » 1)

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            # i >> 1 divides by 2, then add 1 if i is odd
            ans[i] = ans[i >> 1] + (i & 1)
        return ans

Approach 3: Offset Pattern

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        offset = 1

        for i in range(1, n + 1):
            if offset * 2 == i:
                offset = i
            ans[i] = 1 + ans[i - offset]

        return ans

Approach 4: Naive (Not Optimal)

class Solution:
    def countBits(self, n: int) -> List[int]:
        def count_ones(num):
            count = 0
            while num:
                count += num & 1
                num >>= 1
            return count

        return [count_ones(i) for i in range(n + 1)]

Complexity Analysis

DP Approaches:

Time Complexity: O(n), single pass through numbers 0 to n.
Space Complexity: O(1) excluding output array.

Naive Approach:

Time Complexity: O(n log n), counting bits for each number.
Space Complexity: O(1) excluding output array.

Key Insights

i & (i-1) Pattern: Removes the rightmost set bit, creating recurrence: count[i] = count[i & (i-1)] + 1
Right Shift Pattern: i >> 1 is i/2. Count for i equals count for i/2 plus 1 if i is odd: count[i] = count[i >> 1] + (i & 1)
Power of 2 Pattern: Numbers can be grouped by powers of 2:
Recurrence Relation: Each number’s bit count relates to a previous number’s count.
Optimal Solution: O(n) time with single pass, O(1) extra space.
No Built-ins Needed: Can solve without popcount or bin().count().
Mathematical Elegance: Binary properties allow us to build solution incrementally using previous results.