easy

Counting Bits

Given an integer n, return an array where entry i (for 0 ≤ i ≤ n) is the number of 1 bits in the binary representation of i. Aim for linear total time.

Constraints
  • 0 ≤ n ≤ 10^5
Examples
in: n = 5
out: [0,1,1,2,1,2]
Recognition clues
  • Answer for every number up to n — reuse smaller answers
  • Removing the lowest set bit: i & (i − 1) has one fewer 1
  • Or: i >> 1 has the same bits except the lowest
Pattern
Bit Manipulation

XOR cancels pairs, so "every element appears twice except one" is a single XOR pass with no extra memory. Sets of at most ~20 items fit in an integer bitmask, turning subset enumeration and "which nodes have been visited" states into cheap arithmetic that DP and BFS can index directly.

Count Set Bits (Popcount)Bitwise Operators1D (Linear) DP
Solution

Fill an array with bits[0] = 0 and, for each i ≥ 1, bits[i] = bits[i & (i - 1)] + 1, since clearing the lowest set bit yields a smaller number with exactly one fewer 1. Equivalently bits[i] = bits[i >> 1] + (i & 1). Each entry is computed in constant time from an earlier one.

time O(n)space O(n) for the output
Alternative approaches
  • Calling a popcount routine per number costs O(n log n) bit operations; hardware popcount makes it fast in practice.
Code it yourself
Solve in
Hints:
Learn XOR Patterns▶ Visualize