DSAPrep
EasyBit Manipulation

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.

Do not solve it with built-in functions (i.e., like __builtin_popcount in C++).

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?
View original on LeetCode ↗

Counting the set bits of a single number takes O(log n) time, so counting them for every number from 0 to n independently costs O(n log n). The follow-up asks for O(n) — the way there is to notice that the answer for i can be built from an answer you already computed for a smaller number, which is exactly the 1-D DP pattern from problems like Climbing Stairs.

Popcount Every Number

Time O(n log n)Space O(1) extra

For each i from 0 to n, count its set bits from scratch using the n & (n-1) trick (clears the lowest set bit each iteration, one iteration per set bit).

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

Each call to popcount(i) costs up to O(log i) work, and this is repeated for all n + 1 numbers, giving O(n log n) time. No per-number result is reused, even though popcount(6) and popcount(3) are closely related (6 is just 3 shifted left by one bit).

1-D DP: Build from a Smaller Answer

OptimalTime O(n)Space O(n)

Every integer i relates to a smaller integer already in the table via a right shift: i >> 1 drops i’s lowest bit, and that dropped bit is exactly i & 1. So the number of set bits in i is the number of set bits in i >> 1, plus one more if i is odd:

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

This is a bottom-up DP exactly like Climbing Stairs’ dp[i] = dp[i-1] + dp[i-2] — each entry is computed in O(1) from an entry already filled earlier in the array (since i >> 1 < i for all i >= 1).

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

The dp array filling in for n = 5:

0
0
·
1
·
2
·
3
·
4
·
5
1 / 6
comparingseenresult

Base case: dp[0] = 0, since 0 has no set bits.

Correctness: dropping the lowest bit of i via i >> 1 always yields a smaller, already-computed index, and re-adding that bit’s contribution (i & 1) recovers the exact count for i.

Complexity: one pass, O(1) work per index using only already-filled table entries → O(n) time, matching the follow-up. The output array itself is O(n) space (unavoidable, since the array is the required output).