Log inSign up
easyLeetCodeNot Started

Counting Bits

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

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.

You should solve it in linear time O(n) in a single pass without using any built-in functions.

Example 1 · Example 1: n = 2:

Input: n = 2
Output: [0, 1, 1]
Explanation: 0 --> 0 (0 ones), 1 --> 1 (1 one), 2 --> 10 (1 one).

Example 2 · Example 2: n = 5:

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation: 0 -> 0, 1 -> 1, 2 -> 1, 3 -> 2, 4 -> 1, 5 -> 2.

Constraints:

  • 0 <= n <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Discover dynamic programming recurrence relations embedded in binary arithmetic.
  • Compare LSB transition ans[i >> 1] + (i & 1) vs Kernighan transition ans[i & (i - 1)] + 1.
  • Achieve single-pass O(n) performance without library popcount calls.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Need bit counts for all values in range [0, n].
  • Follow-up requires O(n) linear time in a single pass.
  • Overlapping bit subproblems between integers.

Algorithmic Decision Tree:

  • Initialize ans = new int[n + 1].
  • Loop i from 1 to n: ans[i] = ans[i >> 1] + (i & 1).

Connected Patterns:

Count Set BitsNumber of 1 BitsSubsets

1. Individual Popcount Simulation

Intuition

Allocate array ans of size n + 1. For each index i from 0 to n, run Brian Kernighan's bit-clearing loop on i to compute its set bit count.

When to apply: Baseline comparison without dynamic programming.

Algorithm

  1. Step 1: Allocate ans array of size n + 1.
  2. Step 2: Loop i from 0 to n.
  3. Step 3: Count set bits of i using temp &= (temp - 1).
  4. Step 4: ans[i] = count.
  5. Step 5: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6vector<int> countBitsBrute(int n) {
7 vector<int> ans(n + 1, 0);
8 for (int i = 0; i <= n; ++i) {
9 int temp = i;
10 int count = 0;
11 while (temp > 0) {
12 temp &= (temp - 1);
13 count++;
14 }
15 ans[i] = count;
16 }
17 return ans;
18}
19
20int main() {
21 auto res = countBitsBrute(5);
22 cout << "Brute (5): ";
23 for (int v : res) cout << v << " ";
24 cout << endl; // 0 1 1 2 1 2
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(n log n)
  • Space complexity: O(1) auxiliary space

2. DP with Rightmost Set Bit (Kernighan Transition)

Intuition

Notice that i & (i - 1) drops the lowest set bit from i. Because i & (i - 1) < i, its bit count is already computed in ans. Adding 1 for the dropped bit gives ans[i] = ans[i & (i - 1)] + 1.

When to apply: When using previous bit patterns without division.

Algorithm

  1. Step 1: Allocate ans array of size n + 1.
  2. Step 2: ans[0] = 0.
  3. Step 3: Loop i from 1 to n: ans[i] = ans[i & (i - 1)] + 1.
  4. Step 4: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6vector<int> countBitsKernighanDP(int n) {
7 vector<int> ans(n + 1, 0);
8 for (int i = 1; i <= n; ++i) {
9 ans[i] = ans[i & (i - 1)] + 1;
10 }
11 return ans;
12}
13
14int main() {
15 auto res = countBitsKernighanDP(5);
16 cout << "Kernighan DP (5): ";
17 for (int v : res) cout << v << " ";
18 cout << endl; // 0 1 1 2 1 2
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

3. DP with Least Significant Bit (Right Shift)

Intuition

Right shifting i gives i >> 1, which contains all bits of i except the lowest bit. The lowest bit is retrieved via i & 1. Since i >> 1 < i, ans[i >> 1] is already memoized in the array. This yields a single-operation update with zero branches.

When to apply: Optimal canonical solution for Counting Bits.

Algorithm

  1. Step 1: Allocate ans array of size n + 1.
  2. Step 2: Initialize ans[0] = 0.
  3. Step 3: Loop i from 1 to n: ans[i] = ans[i >> 1] + (i & 1).
  4. Step 4: Return ans.

DP Right-Shift Trace for n = 5

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Base case: ans[0] = 0
Visual state
Values and pointers at this exact step
pointers
S
0
0
↑ i = 0
Check / comparison
ans[0] = 0
Decision / next transition
Seed DP table.
Why this step matters

Base case: ans[0] = 0.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 vector<int> countBits(int n) {
9 vector<int> ans(n + 1, 0);
10 for (int i = 1; i <= n; ++i) {
11 ans[i] = ans[i >> 1] + (i & 1);
12 }
13 return ans;
14 }
15};
16
17int main() {
18 Solution sol;
19 auto res = sol.countBits(5);
20 cout << "Optimal (5): ";
21 for (int v : res) cout << v << " ";
22 cout << endl; // 0 1 1 2 1 2
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Individual PopcountO(n log n)O(1) auxiliaryLoop through each integer from 0 to n and independently call Kernighan's bit count.Independent bit counting per number.
2.Better — DP with Power-of-Two OffsetO(n)O(1) auxiliaryTrack current power-of-2 offset: ans[i] = ans[i - offset] + 1, doubling offset when i == 2 * offset.Offset state management.
3.Optimal — DP with Right Shift (LSB)OptimalO(n)O(1) auxiliaryans[i] = ans[i >> 1] + (i & 1). Directly links i to i/2 in a single instruction.Memory write for output array.

Common Pitfalls & Crucial Edge Cases

Calling built-in popcount in a loop

While O(n * 32) passes, interviewers specifically ask for O(n) single-pass dynamic programming without built-ins.

Incorrect base case

Failing to initialize ans[0] = 0.

Index out of bounds

Referencing ans[i - (1 << k)] without properly tracking the current power of two.

Crucial Edge Cases to Validate:

  • n = 0 — Returns [0].
  • n = 1 — Returns [0, 1].
  • Powers of two (i = 2, 4, 8, 16) — Exactly one set bit; ans[i] = ans[i/2] = 1.
  • n = 10^5 — Must construct the full array in O(n) time without overhead.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the recurrence relation ans[i] = ans[i >> 1] + (i & 1) as the most elegant transition.
  2. Also mention the alternative ans[i] = ans[i & (i - 1)] + 1 to demonstrate mastery of bit properties.
  3. Highlight that this achieves linear O(n) time compared to the naive O(n log n) approach.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What dynamic programming recurrence relates the number of set bits in i to an earlier computed value?

2.What alternative recurrence uses Brian Kernighan's trick for dynamic programming?

3.What is the overall time and auxiliary space complexity for Counting Bits up to n?

Back to DSA Sheet