Problem 34.3 · Bit ManipulationEasy

Counting Bits

PatternBit Manipulation 1D Dynamic Programming

What it teaches: A DP over numbers: bits(i) = bits(i >> 1) + (i & 1).

Practise it on judges as “Counting Bits”.

The problem

Return an array ans of length n + 1 where ans[i] is the number of 1 bits in i.

Example 1

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]

Constraints

0 ≤ n ≤ 10⁵

Pattern clues in the wording

→ Bit counts for every number up to n

These clues point to Bit Manipulation: Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int[] countBits(int n) {
        return new int[n + 1];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 2	[0,1,1]
2	n = 5	[0,1,1,2,1,2]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Shift DP · O(n)

Shift DP

Time O(n) Space O(1) besides the output

ans[i] = ans[i >> 1] + (i & 1).

Approach 1

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
        return ans;
    }
}

Verdict: Each value from a smaller one.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 0 ([0])

Mistakes people make

Counting each number separately (O(n log n), fine but not the point).

Interview

Follow-up questions

Another recurrence?

Command Palette

The problem

Approaches

Shift DP

Edge cases and common mistakes

Follow-up questions