How do you approach Counting Bits?

You could count the bits of every number independently, but that repeats work - the bits of i are closely related to the bits of a smaller number you already solved.

What is the time complexity of Counting Bits?

Time complexity: O(n) - one constant-time step per number. Space complexity: O(n) - the output array (no extra space beyond it).

What are common mistakes on Counting Bits?

Shifting by at least the word width, which is undefined or wraps depending on the language. Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends. Precedence: & and | bind more loosely than the comparison operators, so a & 1 == 0 does not mean what it looks like.

Sitelet https://gitgood.dev/coding/counting-bits

gitGood.dev

← Back to problems

Counting Bits

EasyAlgorithms

Description

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 bits in the binary representation of i.

Example 1

Input: n = 2

Output: [0,1,1]

Explanation: 0 -> 0b0 has 0 one-bits, 1 -> 0b1 has 1, 2 -> 0b10 has 1.

Example 2

Input: n = 5

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

Explanation: 5 -> 0b101 has 2 one-bits.

Example 3

Input: n = 0

Output: [0]

Constraints

- 0 <= n <= 10^5

Counting Bits: approach, complexity and pitfalls

An easy bit manipulation problem, graded against 6 test cases (3 of them hidden).

The pattern: Bit Manipulation

XOR, masks, and shifts - constant-space tricks for counting and pairing.

Reach for it when you see: "Appears once/twice", powers of two, or an explicit O(1) space requirement.

If you are stuck

Show the 3-step hint ladder

You could count the bits of every number independently, but that repeats work - the bits of i are closely related to the bits of a smaller number you already solved.
Removing the lowest bit of i gives i >> 1. How does the bit count of i relate to the bit count of i >> 1?
ans[i] = ans[i >> 1] + (i & 1). Build the array from 0 up to n.

The optimal approach

Show the approach: DP on the Bit Pattern

Every number `i` shares its binary digits with `i >> 1` (i shifted right by one), plus possibly a trailing 1. So `ans[i] = ans[i >> 1] + (i & 1)`. Building the table left to right answers every prefix in constant time per entry.

Time: O(n) - one constant-time step per number
Space: O(n) - the output array (no extra space beyond it)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Bit Manipulation mistakes

These apply to the pattern as a whole, not just this problem.

Shifting by at least the word width, which is undefined or wraps depending on the language.
Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends.
Precedence: `&` and `|` bind more loosely than the comparison operators, so `a & 1 == 0` does not mean what it looks like.