146.Counting Bits

EasyBlind 75Bit Manipulation · 3/7

Problem

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n.

Follow-up: can you do it in O(n) time in a single pass, without a built-in popcount?

Examples

Input:  n = 2
Output: [0, 1, 1]
Explanation:
0 → 0    (0 ones)
1 → 1    (1 one)
2 → 10   (1 one)

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

💡 Key Insight

Every number's bit count is closely related to a smaller number we have already solved. Shifting i right by one drops its last bit, so bits(i) = bits(i >> 1) + (i & 1). Since i >> 1 < i, filling the array from left to right turns this into a simple DP with O(1) work per entry.

Brute Force (Count Each Number)

TimeO(n log n)SpaceO(1) extra (the output array is required).

Intuition

Solve Number of 1 Bits independently for each i from 0 to n, using Kernighan's x & (x - 1) trick to clear one set bit at a time.

Algorithm

Create ans of size n + 1.
For each i, copy x = i; while x != 0, do x &= x - 1 and increment ans[i].
Return ans.

Visualization

i = 5 (101): 101 → 100 → 000   → 2 ones
i = 4 (100): 100 → 000         → 1 one
i = 3 (011): 011 → 010 → 000   → 2 ones

Code

java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int x = i;
            while (x != 0) {
                x &= x - 1; // drop lowest set bit
                ans[i]++;
            }
        }
        return ans;
    }
}

Complexity

Time: O(n log n) — each number has at most log2(n) + 1 set bits.
Space: O(1) extra (the output array is required).

DP with Most-Significant-Bit Offset

TimeO(n)SpaceO(1) extra.

Intuition

Numbers in the block [2^k, 2^(k+1)) look exactly like the numbers [0, 2^k) with one extra leading 1. So ans[i] = 1 + ans[i - offset], where offset is the largest power of two <= i. We track offset and double it whenever i reaches the next power of two.

Algorithm

ans[0] = 0, offset = 1.
For i from 1 to n:
- If offset * 2 == i, set offset = i.
- ans[i] = 1 + ans[i - offset].
Return ans.

Visualization

i : 0  1  2  3  4  5  6  7  8
off:   1  2  2  4  4  4  4  8
ans: 0  1  1  2  1  2  2  3  1
         ↑     ↑  ↑
     ans[3] = 1 + ans[3-2] = 1 + 1 = 2
     ans[4] = 1 + ans[4-4] = 1 + 0 = 1
     ans[5] = 1 + ans[5-4] = 1 + 1 = 2

Code

java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        int offset = 1; // largest power of two <= i
        for (int i = 1; i <= n; i++) {
            if (offset * 2 == i) {
                offset = i; // reached the next power of two
            }
            ans[i] = 1 + ans[i - offset]; // leading 1 + the remaining low bits
        }
        return ans;
    }
}

Complexity

Time: O(n) — constant work per index.
Space: O(1) extra.

DP with Right ShiftOptimal

TimeO(n)SpaceO(1) extra (only the required output).

Intuition

i >> 1 is i with its last bit removed, and i & 1 is that removed bit. Therefore ans[i] = ans[i >> 1] + (i & 1). The referenced index i >> 1 is always smaller than i, so it is already computed. No power-of-two bookkeeping is needed.

(An equivalent recurrence is ans[i] = ans[i & (i - 1)] + 1, which removes the lowest set bit instead of the last bit.)

Algorithm

ans[0] = 0.
For i from 1 to n: ans[i] = ans[i >> 1] + (i & 1).
Return ans.

Dry Run

flowchart LR
    A["ans[0] = 0"] --> B["ans[1] = ans[0] + 1 = 1"]
    B --> C["ans[2] = ans[1] + 0 = 1"]
    C --> D["ans[3] = ans[1] + 1 = 2"]
    D --> E["ans[4] = ans[2] + 0 = 1"]
    E --> F["ans[5] = ans[2] + 1 = 2"]
    F --> G["result [0,1,1,2,1,2]"]

i	binary	i >> 1	i & 1	ans[i]
0	0	–	–	0
1	1	0	1	1
2	10	1	0	1
3	11	1	1	2
4	100	2	0	1
5	101	2	1	2

Code

java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // bits of i = bits of i without its last bit + the last bit itself
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

Complexity

Time: O(n) — one O(1) step per index.
Space: O(1) extra (only the required output).

Complexity Comparison

Approach	Time	Space
Count Each Number	O(n log n)	O(1)
DP with MSB Offset	O(n)	O(1)
DP with Right Shift	O(n)	O(1)

Common Pitfalls

Allocating an array of size n instead of n + 1 — the answer must include i = n.
Writing ans[i >> 1] + i & 1 without parentheses — + binds tighter than &, so it computes (ans[i >> 1] + i) & 1.
In the offset approach, updating offset after using it — at i = 4 you must switch to offset = 4 first, otherwise ans[4] = 1 + ans[2] = 2 (wrong).
Forgetting n = 0 — the result is simply [0]; all three solutions handle it because the loop never runs.