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

Topics

Dynamic Programming Bit Manipulation

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.

Prerequisites

Before attempting this problem, you should be comfortable with:

Bit Manipulation - Understanding binary representation and bitwise operations (AND, OR, shifts)
Dynamic Programming - Building solutions incrementally using previously computed results
Binary Number System - Understanding how integers are represented in binary and counting set bits

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

public class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int num = 1; num <= n; num++) {
            for (int i = 0; i < 32; i++) {
                if ((num & (1 << i)) != 0) {
                    res[num]++;
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1);
        for (int num = 1; num <= n; num++) {
            for (int i = 0; i < 32; i++) {
                if (num & (1 << i)) {
                    res[num]++;
                }
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number[]}
     */
    countBits(n) {
        let res = [];
        for (let num = 0; num <= n; num++) {
            let one = 0;
            for (let i = 0; i < 32; i++) {
                if ((num & (1 << i)) != 0) {
                    one++;
                }
            }
            res.push(one);
        }
        return res;
    }
}

public class Solution {
    public int[] CountBits(int n) {
        int[] res = new int[n + 1];
        for (int num = 1; num <= n; num++) {
            for (int i = 0; i < 32; i++) {
                if ((num & (1 << i)) != 0) {
                    res[num]++;
                }
            }
        }
        return res;
    }
}

func countBits(n int) []int {
    res := make([]int, n+1)
    for num := 0; num <= n; num++ {
        one := 0
        for i := 0; i < 32; i++ {
            if num&(1<<i) != 0 {
                one++
            }
        }
        res[num] = one
    }
    return res
}

class Solution {
    fun countBits(n: Int): IntArray {
        val res = IntArray(n + 1)
        for (num in 0..n) {
            var one = 0
            for (i in 0 until 32) {
                if (num and (1 shl i) != 0) {
                    one++
                }
            }
            res[num] = one
        }
        return res
    }
}

class Solution {
    func countBits(_ n: Int) -> [Int] {
        var res = [Int]()
        for num in 0...n {
            var one = 0
            for i in 0..<32 {
                if num & (1 << i) != 0 {
                    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

public class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int num = i;
            while (num != 0) {
                res[i]++;
                num &= (num - 1);
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            int num = i;
            while (num != 0) {
                res[i]++;
                num &= (num - 1);
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number[]}
     */
    countBits(n) {
        let res = new Array(n + 1).fill(0);
        for (let i = 1; i <= n; i++) {
            let num = i;
            while (num !== 0) {
                res[i]++;
                num &= num - 1;
            }
        }
        return res;
    }
}

public class Solution {
    public int[] CountBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int num = i;
            while (num != 0) {
                res[i]++;
                num &= (num - 1);
            }
        }
        return res;
    }
}

func countBits(n int) []int {
    res := make([]int, n+1)
    for i := 1; i <= n; i++ {
        num := i
        for num != 0 {
            res[i]++
            num &= (num - 1)
        }
    }
    return res
}

class Solution {
    fun countBits(n: Int): IntArray {
        val res = IntArray(n + 1)
        for (i in 1..n) {
            var num = i
            while (num != 0) {
                res[i]++
                num = num and (num - 1)
            }
        }
        return res
    }
}

class Solution {
    func countBits(_ n: Int) -> [Int] {
        var res = [Int](repeating: 0, count: n + 1)
        for i in 1..<(n + 1) {
            var 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)]

public class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = Integer.bitCount(i);
        }
        return res;
    }
}

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1, 0);
        for (int i = 0; i <= n; i++) {
            res[i] = __builtin_popcount(i);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number[]}
     */
    countBits(n) {
        let res = [];
        for (let i = 0; i <= n; i++) {
            res.push(i.toString(2).split('1').length - 1);
        }
        return res;
    }
}

class Solution {
    func countBits(_ n: Int) -> [Int] {
        var res = [Int](repeating: 0, count: n + 1)
        for num in 1..<(n + 1) {
            res[num] = num.nonzeroBitCount
        }
        return res
    }
}

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

public class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        int offset = 1;

        for (int i = 1; i <= n; i++) {
            if (offset * 2 == i) {
                offset = i;
            }
            dp[i] = 1 + dp[i - offset];
        }
        return dp;
    }
}

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1);
        int offset = 1;

        for (int i = 1; i <= n; i++) {
            if (offset * 2 == i) {
                offset = i;
            }
            dp[i] = 1 + dp[i - offset];
        }
        return dp;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number[]}
     */
    countBits(n) {
        const dp = new Array(n + 1).fill(0);
        let offset = 1;

        for (let i = 1; i <= n; i++) {
            if (offset * 2 == i) {
                offset = i;
            }
            dp[i] = 1 + dp[i - offset];
        }
        return dp;
    }
}

public class Solution {
    public int[] CountBits(int n) {
        int[] dp = new int[n + 1];
        int offset = 1;

        for (int i = 1; i <= n; i++) {
            if (offset * 2 == i) {
                offset = i;
            }
            dp[i] = 1 + dp[i - offset];
        }
        return dp;
    }
}

func countBits(n int) []int {
    dp := make([]int, n+1)
    offset := 1

    for i := 1; i <= n; i++ {
        if offset*2 == i {
            offset = i
        }
        dp[i] = 1 + dp[i - offset]
    }
    return dp
}

class Solution {
    fun countBits(n: Int): IntArray {
        val dp = IntArray(n + 1)
        var offset = 1

        for (i in 1..n) {
            if (offset * 2 == i) {
                offset = i
            }
            dp[i] = 1 + dp[i - offset]
        }
        return dp
    }
}

class Solution {
    func countBits(_ n: Int) -> [Int] {
        var dp = [Int](repeating: 0, count: n + 1)
        var offset = 1

        for i in 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

class Solution {
    /**
     * @param {number} n
     * @return {number[]}
     */
    countBits(n) {
        let dp = new Array(n + 1).fill(0);
        for (let i = 1; i <= n; i++) {
            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