Skip to main content

338. Counting Bits

easy

For every integer in [0, n], return the count of set bits. The textbook DP-meets-bit-manipulation: bits(i) = bits(i >> 1) + (i & 1). Linear time, beats the per-number Kernighan baseline.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 0 <= n <= 10^5

Examples

Example 1

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

Explanation: 0 --> 0; 1 --> 1; 2 --> 10.

Example 2

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

Explanation: 0 --> 0; 1 --> 1; 2 --> 10; 3 --> 11; 4 --> 100; 5 --> 101.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Baseline: call Brian Kernighan's algorithm for each i. O(n log n) total.

Hint 2

DP: bits(i) = bits(i >> 1) + (i & 1). The right shift drops the lowest bit; whether it was set is i & 1.

Hint 3

Alternative DP: bits(i) = bits(i & (i - 1)) + 1. Use the Kernighan identity that i & (i - 1) drops the lowest set bit.

Hint 4

Either DP is O(n) overall — each entry computed in O(1) from an earlier entry.

Solution approach

Reveal approach

DP. Allocate ans[0..n]. ans[0] = 0. For i from 1 to n: ans[i] = ans[i >> 1] + (i & 1). The recurrence works because the binary representation of i, except for its lowest bit, equals the binary representation of i >> 1 — so the set bits are 'set bits of (i >> 1)' plus 'whether the lowest bit of i is set'. Return ans. O(n) time, O(n) space for the output. The alternative DP ans[i] = ans[i & (i - 1)] + 1 leverages Kernighan's drop-lowest-set-bit identity; equally O(n). Both are interview-grade — the i >> 1 version is more intuitive, the Kernighan version a bit slicker.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • dynamic-programming
  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Counting Bits and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →