Skip to main content

338. Counting Bits

easy

For every integer from 0 to n, count the number of set bits. The O(n) DP-on-bits recurrence: ans[i] = ans[i >> 1] + (i & 1).

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

The brute force calls popcount on every i from 0 to n — O(n log n).

Hint 2

Look for a recurrence between i and a smaller value you've already computed.

Hint 3

ans[i] = ans[i >> 1] + (i & 1): the bits of i are the bits of i/2 shifted by one, plus the lowest bit of i.

Hint 4

Alternative recurrence using Kernighan: ans[i] = ans[i & (i - 1)] + 1.

Solution approach

Reveal approach

DP-on-bits. Allocate ans of size n + 1 with ans[0] = 0. For i from 1 to n, set ans[i] = ans[i >> 1] + (i & 1). The recurrence works because dropping the lowest bit (i >> 1) gives a smaller index whose popcount we already computed, and we just add back the lowest bit of i. One pass, O(n) time, O(1) extra space (excluding the output array). The Kernighan variant ans[i] = ans[i & (i - 1)] + 1 also works in O(n) and is equally elegant.

Complexity

Time
O(n)
Space
O(1) extra

Related patterns

  • bit-manipulation
  • dynamic-programming

Related problems

Asked at

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

  • Amazon
  • Google
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →