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 Sam K., 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

More Math practice problems

See all Math problems →