← DSA Atlas
Dedicated problem page · #338

Counting Bits

EasyBit ManipulationDP on bit countDynamic programming with bit shifting
Solve on LeetCode ↗
338
EasyBit ManipulationDynamic programming with bit shiftingDP on bit count

Counting Bits

Given an integer n, return an array of length n + 1 where the element at index i is the number of 1 bits (the popcount) in the binary representation of i.

Open official problem prompt ↗
In plain English

Build the full table of set-bit counts for 0..n in one linear sweep instead of counting each number from scratch.

Picture it like this

To count coins in each of many jars, you notice each jar is just a previous jar with one more coin poured off the top. Instead of recounting a jar, you take the known count of the smaller jar and add back the single coin you removed.

Example
Input
n = 2
Output
[0, 1, 1]
Why
0 = 0b0 has zero 1s, 1 = 0b1 has one, 2 = 0b10 has one.
Constraints
0 <= n <= 10^5
Pattern lesson

See the pattern, then code

DP on bit count
Recognition clue

You must produce popcounts for every value from 0 to n, and the follow-up asks for a single linear pass without a per-number counting loop — that hints at reusing already-computed answers.

↗
Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. Dropping the lowest bit of i (i >> 1) gives a smaller number whose popcount you already computed; i just has one extra bit — the one you dropped — which is 1 exactly when i is odd. So ans[i] = ans[i >> 1] + (i & 1).

New words, made simpleKnow these before the algorithm
Popcount
The number of 1 bits in a value's binary form.
Right shift (i >> 1)
Integer division by two, which discards the lowest bit.
i & 1
Extracts the lowest bit: 1 if i is odd, 0 if even.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Count each number independently

Works but does redundant work the follow-up asks you to avoid.

For every i, loop over its bits (or call bin(i).count('1')).

Time O(n log n)Space O(1)
Best choiceDP on the shifted value

Single linear pass, each entry computed in O(1).

ans[i] = ans[i >> 1] + (i & 1), reusing the already-known smaller answer.

Time O(n)Space O(1)
The rule we keep true

Invariant

When computing ans[i], the index i >> 1 is strictly smaller than i, so ans[i >> 1] is already finalized and correct.

Why this is correct

Reasoning

Every integer i equals (i >> 1) shifted left by one, with its lowest bit re-added. Left-shifting preserves the number of 1 bits, so popcount(i) = popcount(i >> 1) + (lowest bit of i), and the lowest bit is i & 1.

The algorithm in three movesSay these aloud before coding
1Allocate ans of size n + 1 filled with 0

ans[0] = 0

2For each i from 1 to n, set ans[i] = ans[i >> 1] + (i & 1)

ans[1] = ans[0] + (1&1) = 0 + 1 = 1

3Return ans

ans[2] = ans[1>>1=1... 2>>1=1] wait: ans[2] = ans[1] + (2&1) = 1 + 0 = 1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
102
1 · Readn = 2
2 · AskWhat is the base case?
3 · Update stateans = [0, 0, 0]
4 · Resultans[0] = 0 needs no work
Key takeaway

Each value's popcount reuses the popcount of the same number with its last bit removed, plus that last bit.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Allocate the table

    ans[0] is correctly 0 by initialization, serving as the base case.

  2. 2
    Lines 4-5Fill via recurrence

    Each entry reads a strictly-earlier, already-final entry (i >> 1) and adds the dropped low bit.

  3. 3
    Lines 6Return the completed table

    Every index now holds its popcount.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • n = 0 returns [0]
  • Powers of two like 4 have popcount 1
  • n = 1 returns [0, 1]
!

Common beginner mistakes

  • Sizing the array as n instead of n + 1 and dropping the last entry
  • Using bin(i).count('1') in the loop, which technically works but misses the intended O(n) recurrence
  • Confusing i >> 1 (drop lowest bit) with i & (i - 1) (also valid via a different recurrence, but then you add 1 not i & 1)
Check your understanding

Why is the DP array guaranteed to have ans[i >> 1] already computed when filling ans[i]?

More in Bit Manipulation

#50Pow(x, n)Fast exponentiation (binary exponentiation)#89Gray CodeBinary-to-Gray transform (i XOR i>>1)#136Single NumberXOR cancellation#137Single Number IIBitwise finite-state counting (mod-3 per bit)#190Reverse BitsBit-by-bit reversal accumulation#191Number of 1 BitsBrian Kernighan bit clearing