Counting Bits

MediumBit Manipulationbit DP

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given a non-negative integer n, build a list result of length n + 1 where result[i] holds the number of 1 bits in the binary representation of i, for every i from 0 through n inclusive. For example, the number 5 is 101 in binary and therefore contains two set bits. Returning the answer is straightforward if you call a built-in popcount for each value, but the intended challenge is to compute every entry in a single linear pass. Aim for an O(n) runtime by reusing the counts you have already computed for smaller indices, rather than recounting the bits of each number from scratch.

Examples

Input: n = 2
Output: [0, 1, 1]
0 -> 0 (zero set bits), 1 -> 1 (one set bit), 2 -> 10 (one set bit).
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Counting set bits for 0..5: 0, 1, 1, 2 (11), 1 (100), 2 (101).
Input: n = 0
Output: [0]
The only value is 0, which has no set bits.

Constraints

  • 0 <= n <= 100000
  • The returned list must have exactly n + 1 entries.
  • Index i of the result corresponds to the integer i.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.