Skip to main content

18. Counting Bits

easyAsked at Databricks

Count set bits for every integer 0–n — a DP warm-up that directly parallels how Databricks computes per-partition popcount statistics in Photon's vectorized execution engine.

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

Problem

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1s in the binary representation of i.

Constraints

  • 0 <= n <= 10^5

Examples

Example 1

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

Explanation: 0 → 0 bits, 1 → 1 bit, 2 (10) → 1 bit.

Example 2

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

Approaches

1. Naive popcount per number

For each i, count bits with a Brian Kernighan loop. O(n log n) total.

Time
O(n log n)
Space
O(1) auxiliary
function countBits(n) {
  const ans = new Array(n + 1);
  for (let i = 0; i <= n; i++) {
    let x = i, cnt = 0;
    while (x > 0) { x &= x - 1; cnt++; }
    ans[i] = cnt;
  }
  return ans;
}

Tradeoff:

2. DP with lowest-set-bit recurrence

ans[i] = ans[i >> 1] + (i & 1). Each number's bit count is its right-shifted value's count plus the parity of its lowest bit. Single pass, O(n).

Time
O(n)
Space
O(1) auxiliary
function countBits(n) {
  const ans = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i >> 1] + (i & 1);
  }
  return ans;
}

Tradeoff:

Databricks-specific tips

At Databricks, the DP recurrence matters less than your ability to derive it from first principles on a whiteboard. Walk through a concrete power-of-two (e.g., i=4) to show the pattern before writing code — interviewers score derivation equally with the final solution.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Counting Bits and other Databricks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →