‹ DS&A interview · Socratic
DSA · Bit Manipulation · #61

Counting Bits

Module 50 · difficulty 2/5·⏱ 30:00starts on first keystroke

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`s in the binary representation of `i` (its popcount). Implement `function countBits(n)` returning the array.

Examples
  • n = 2 → [0, 1, 1] — 0 -> 0b0 (0 ones), 1 -> 0b1 (1 one), 2 -> 0b10 (1 one).
  • n = 5 → [0, 1, 1, 2, 1, 2] — 3 -> 0b11 (2 ones), 4 -> 0b100 (1 one), 5 -> 0b101 (2 ones).
  • n = 0 → [0] — Only index 0, which has zero set bits.
Constraints
  • · 0 <= n <= 10^5
  • · The returned array has exactly n + 1 elements.
  • · ans[i] equals the popcount of i.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.