Counting Bits

Difficulty: Easy | Acceptance: 80.60% | Paid: No Topics: Dynamic Programming, Bit Manipulation

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.

• Examples
• Constraints
• Approach 1: Brute Force (Brian Kernighan’s Algorithm)
• Approach 2: Dynamic Programming (Most Significant Bit)
• Approach 3: Dynamic Programming (Lowest Set Bit)
• Approach 4: Dynamic Programming (Bit Shifting)

Examples

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⁵

Approach 1: Brute Force (Brian Kernighan’s Algorithm)

Intuition Iterate through every number from 0 to n. For each number, count the number of set bits (1s) using Brian Kernighan’s algorithm, which repeatedly clears the least significant set bit.

Steps

• Initialize an array ans of size n + 1.
• Loop from i = 0 to n.
• For each i, initialize a count variable.
• While i > 0, perform i = i & (i - 1) to clear the lowest set bit and increment count.
• Store count in ans[i].
• Return ans.

class Solution:
    def countBits(self, n: int) -> list[int]:
        ans = [0] * (n + 1)
        for i in range(n + 1):
            count = 0
            x = i
            while x:
                x &= x - 1
                count += 1
            ans[i] = count
        return ans

Complexity

• Time: O(n log n)
• Space: O(1) (excluding output array)
• Notes: Simple to implement but slower for large n due to the inner loop.

Approach 2: Dynamic Programming (Most Significant Bit)

Intuition For a number i, find the largest power of 2 less than or equal to i (let’s call it b). The number of 1s in i is equal to the number of 1s in i - b plus 1 (for the MSB itself).

Steps

• Initialize ans array with ans[0] = 0.
• Initialize offset = 1 (represents 2⁰).
• Loop from i = 1 to n.
• If offset * 2 == i, update offset to i (we found the next power of 2).
• Set ans[i] = ans[i - offset] + 1.
• Return ans.

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] = ans[i - offset] + 1
        return ans

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Efficient linear time solution using the properties of binary numbers.

Approach 3: Dynamic Programming (Lowest Set Bit)

Intuition The operation x & (x - 1) clears the lowest set bit in x. Therefore, ans[x] = ans[x & (x - 1)] + 1. This reuses the result of the number with the lowest bit removed.

Steps

• Initialize ans array with ans[0] = 0.
• Loop from i = 1 to n.
• Calculate ans[i] using the formula ans[i] = ans[i & (i - 1)] + 1.
• Return ans.

class Solution:
    def countBits(self, n: int) -> list[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i & (i - 1)] + 1
        return ans

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Very concise and efficient, leveraging bit manipulation directly in the DP relation.

Approach 4: Dynamic Programming (Bit Shifting)

Intuition When you right shift a number i by 1 (i >> 1), you effectively divide it by 2 and remove the least significant bit. The number of 1s in i is the same as in i >> 1 plus the value of the bit that was shifted out (i & 1).

Steps

• Initialize ans array with ans[0] = 0.
• Loop from i = 1 to n.
• Set ans[i] = ans[i >> 1] + (i & 1).
• Return ans.

class Solution:
    def countBits(self, n: int) -> list[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Another elegant linear solution that relies on the relationship between a number and its half.