338. Counting Bits - Explanation

Description

Given an integer n, count the number of 1's in the binary representation of every number in the range [0, n].

Return an array output where output[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 4

Output: [0,1,1,2,1]

Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100

Constraints:

0 <= n <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the given integer.

Hint 1

A straightforward approach would be to iterate from 0 to n using i, and for each i, iterate through its bits to count the number of set bits. This would result in an O(n \log n) approach. Can you think of a better way? Maybe you should try identifying a pattern by observing the bitwise representation of consecutive numbers.

Hint 2

For example, to compute set bits for 7, add 1 to the count of set bits in 3, which was previously computed by adding 1 to the count of set bits in 1. Observing the pattern, for numbers less than 4, add 1 to the count from two positions before. For numbers less than 8, add 1 to the count from four positions before. Can you derive a dynamic programming relation from this?

Hint 3

We find an offset for the current number based on the number before offset positions. The dynamic programming relation is dp[i] = 1 + dp[i - offset], where dp[i] represents the number of set bits in i. The offset starts at 1 and updates when encountering a power of 2. To simplify the power of 2 check, if offset * 2 equals the current number, we update offset to the current number.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Bit Manipulation - I

Intuition

For every number from 0 to n, we want to compute how many 1 bits appear in its binary representation.

This bit manipulation approach checks each bit position individually:

Integers are typically represented using 32 bits
For each number, we test whether the bit at position i is set using a bit mask

Although this solution is not optimal, it clearly demonstrates how bitwise operations work at a low level.

Algorithm

Initialize an empty list res to store results.
For every number num from 0 to n:
- Initialize a counter one = 0
- For each bit position i from 0 to 31:
  - Check if the i-th bit is set using (1 << i) & num
  - If yes, increment one
- Append one to res
Return the list res

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = []
        for num in range(n + 1):
            one = 0
            for i in range(32):
                if num & (1 << i):
                    one += 1
            res.append(one)
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.

2. Bit Manipulation - II

Intuition

To count the number of 1 bits efficiently, we can use Brian Kernighan’s Algorithm.

The key observation:

The operation n & (n - 1) removes the lowest set bit from n
Repeating this until n becomes 0 counts how many 1 bits are present

This avoids checking all 32 bits for every number.

Algorithm

Create an array res of size n + 1 initialized with 0.
For each number i from 1 to n:
- Set num = i
- While num != 0:
  - Increment res[i]
  - Remove the lowest set bit using num &= (num - 1)
Return res.

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [0] * (n + 1)
        for i in range(1, n + 1):
            num = i
            while num != 0:
                res[i] += 1
                num &= (num - 1)
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.

3. In-Built Function

Intuition

We need to compute the number of set bits (1s) in the binary representation of every number from 0 to n.

Instead of manually counting bits using bit manipulation or dynamic programming, many programming languages provide built-in ways to convert numbers to binary or directly count set bits. Using these built-in features allows us to write a very concise and readable solution.

This approach is especially useful when:

n is small to moderate
clarity is more important than optimal performance
we want a quick and reliable implementation

Algorithm

Initialize an empty result list.
For each number i from 0 to n:
- Convert i to its binary representation using a built-in utility.
- Count the number of 1 bits in that representation.
- Append the count to the result list.
Return the result list.

class Solution:
    def countBits(self, n: int) -> List[int]:
        return [bin(i).count('1') for i in range(n + 1)]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.

4. Bit Manipulation (DP)

Intuition

We want to compute the number of set bits (1s) for all numbers from 0 to n efficiently.

A key observation from binary representation is:

Numbers repeat their bit patterns every time we reach a power of two
When a number is a power of two, it has exactly one 1 bit
Any number i can be written as:
i = highestPowerOfTwo ≤ i + remainder

So, the number of set bits in i is:

1 (for the highest power of two) + number of set bits in the remainder

This allows us to build the solution incrementally using Dynamic Programming, reusing results we have already computed.

Algorithm

Create a DP array dp of size n + 1
- dp[i] will store the number of set bits in i
Initialize:
- dp[0] = 0
- offset = 1 (tracks the most recent power of two)
For each number i from 1 to n:
- If i reaches the next power of two (i == 2 * offset):
  - Update offset = i
- Compute:
```
dp[i] = 1 + dp[i - offset]
```
Return the DP array.

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

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

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.

5. Bit Manipulation (Optimal)

Intuition

We want to find the number of set bits (1s) in every number from 0 to n.

A very important observation from binary representation is:

Right-shifting a number by 1 (i >> 1) removes the least significant bit
(i & 1) tells us whether the last bit of i is 1 or 0

So, the number of set bits in i can be built from a smaller number:

setBits(i) = setBits(i >> 1) + (i & 1)

This means each result depends only on a previously computed value, making it a perfect fit for Dynamic Programming.

Algorithm

Create a DP array dp of size n + 1
- dp[i] stores the number of set bits in i
Initialize dp[0] = 0
For every number i from 1 to n:
- Right shift i by 1 to get i >> 1
- Check the last bit using (i & 1)
- Compute:
```
dp[i] = dp[i >> 1] + (i & 1)
```
Return the DP array

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

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.

Common Pitfalls

Incorrect Bit Shift Operator

When using the DP recurrence dp[i] = dp[i >> 1] + (i & 1), a common mistake is using left shift instead of right shift, or confusing the operator precedence.

# Wrong: Using left shift instead of right shift
dp[i] = dp[i << 1] + (i & 1)  # This accesses invalid indices

# Wrong: Operator precedence issue in some languages
dp[i] = dp[i >> 1 + (i & 1)]  # Addition happens before shift

# Correct
dp[i] = dp[i >> 1] + (i & 1)

Off-by-One in Loop Bounds

The problem asks for bits count from 0 to n inclusive, meaning the result array should have n + 1 elements. A common mistake is creating an array of size n or iterating up to n - 1.

# Wrong: Array too small
dp = [0] * n  # Missing dp[n]

# Wrong: Loop doesn't include n
for i in range(n):  # Should be range(n + 1)

# Correct
dp = [0] * (n + 1)
for i in range(n + 1):
    # process