Skip to main content
CodePeetCodePeet
BLIND 75

Counting Bits

EASYProblemSolveExternal Links

Description

Given a non-negative integer n, return an array ans of length n + 1 where each element ans[i] represents the count of 1 bits (set bits) in the binary representation of the number i.

In other words, for every integer from 0 to n, you need to figure out how many 1s appear when that integer is written in binary form, and collect all those counts into a single array.

Examples

Example 1

Input: n = 2

Output: [0, 1, 1]

Explanation:

  • 0 in binary is 0 → zero 1-bits → ans[0] = 0
  • 1 in binary is 1 → one 1-bit → ans[1] = 1
  • 2 in binary is 10 → one 1-bit → ans[2] = 1

So the result array is [0, 1, 1].

Example 2

Input: n = 5

Output: [0, 1, 1, 2, 1, 2]

Explanation:

  • 0 → 0 → 0 ones
  • 1 → 1 → 1 one
  • 2 → 10 → 1 one
  • 3 → 11 → 2 ones
  • 4 → 100 → 1 one
  • 5 → 101 → 2 ones

Collecting these counts gives [0, 1, 1, 2, 1, 2].

Example 3

Input: n = 0

Output: [0]

Explanation: The only number in the range [0, 0] is 0, which has zero set bits. The result is [0].

Constraints

  • 0 ≤ n ≤ 10^5

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to handle each number independently. For every integer from 0 to n, we count how many 1-bits it has by repeatedly checking its least significant bit and right-shifting.

Imagine you have a row of light switches that are either ON (1) or OFF (0). To count how many are ON, you simply walk along the row from right to left, tally each ON switch, and then move to the next row. That is exactly what we do for each number's binary representation.

Step-by-Step Explanation

Let's trace through with n = 5. For each number 0 through 5, we count its set bits individually.

Step 1: Process number 0.

  • Binary: 0. No 1-bits. count = 0. ans = [0]

Step 2: Process number 1.

  • Binary: 1. Check LSB: 1 & 1 = 1 → count = 1. Right shift: 0. Done. ans = [0, 1]

Step 3: Process number 2.

  • Binary: 10. Check LSB: 0 → count stays 0. Right shift → 1. Check LSB: 1 → count = 1. Right shift → 0. Done. ans = [0, 1, 1]

Step 4: Process number 3.

  • Binary: 11. Check LSB: 1 → count = 1. Right shift → 1. Check LSB: 1 → count = 2. Right shift → 0. Done. ans = [0, 1, 1, 2]

Step 5: Process number 4.

  • Binary: 100. Check LSB: 0. Right shift → 10. Check LSB: 0. Right shift → 1. Check LSB: 1 → count = 1. Right shift → 0. Done. ans = [0, 1, 1, 2, 1]

Step 6: Process number 5.

  • Binary: 101. Check LSB: 1 → count = 1. Right shift → 10. Check LSB: 0. Right shift → 1. Check LSB: 1 → count = 2. Right shift → 0. Done. ans = [0, 1, 1, 2, 1, 2]

Result: [0, 1, 1, 2, 1, 2]

Brute Force — Counting Set Bits One Number at a Time — For each number from 0 to n, we individually count the 1-bits by checking and shifting, then place the count into the result array.

Algorithm

  1. Create a result array ans of size n + 1, initialized to 0.
  2. For each number i from 0 to n:
    a. Set a temporary variable num = i and a counter count = 0.
    b. While num > 0:
    • If the least significant bit is 1 (num & 1 == 1), increment count.
    • Right-shift num by 1 (num >>= 1).
      c. Set ans[i] = count.
  3. Return ans.

Code

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);
        for (int i = 0; i <= n; i++) {
            int num = i;
            int count = 0;
            while (num > 0) {
                count += (num & 1);
                num >>= 1;
            }
            ans[i] = count;
        }
        return ans;
    }
};
class Solution:
    def countBits(self, n: int) -> list[int]:
        ans = [0] * (n + 1)
        for i in range(n + 1):
            num = i
            count = 0
            while num > 0:
                count += num & 1
                num >>= 1
            ans[i] = count
        return ans
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int num = i;
            int count = 0;
            while (num > 0) {
                count += (num & 1);
                num >>= 1;
            }
            ans[i] = count;
        }
        return ans;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

For each of the n + 1 numbers, we inspect up to log₂(i) bits. Summing across all numbers from 0 to n, the total number of bit inspections is proportional to n × log₂(n), giving O(n log n).

Space Complexity: O(1) (excluding the output array)

We only use a couple of temporary variables (num, count). The output array ans of size n + 1 is required by the problem, so it is not counted as extra space.

Why This Approach Is Not Efficient

The brute force approach treats every number as an independent problem, counting its bits from scratch each time. For n = 10^5, this means roughly 10^5 × 17 ≈ 1.7 × 10^6 bit operations — which is fast enough in practice, but the problem explicitly challenges us to achieve O(n) time.

The key inefficiency is that we throw away useful information. When we count the bits for number 5 (binary 101), we already know the bit count for number 2 (binary 10) — it is just 5 right-shifted by one position. The bit count of 5 equals the bit count of 2 plus whatever the last bit of 5 contributes. If we could reuse previously computed answers, we would avoid re-scanning bits we have already analyzed.

This observation — that each number's bit count relates to a smaller number we have already processed — leads us toward a dynamic programming solution.

Optimal Approach - Dynamic Programming (Right Shift Recurrence)

Intuition

Instead of counting bits independently for each number, we can build each answer from a previously computed answer. The insight comes from a simple binary fact:

When you right-shift any number i by one position (i >> 1), you remove its last bit. The remaining bits are identical to the number i >> 1, whose bit count we have already calculated (since i >> 1 < i). The only unknown is whether the removed last bit was a 0 or a 1 — and i & 1 tells us that directly.

So the recurrence is:

ans[i] = ans[i >> 1] + (i & 1)

Think of it like a family tree of numbers. Each number i has a parent i >> 1. The child's set-bit count is the parent's count plus 0 or 1 depending on whether the child is even (last bit 0) or odd (last bit 1). Since we process numbers in order 0, 1, 2, …, the parent's answer is always ready before we need it.

For example:

  • 5 in binary is 101. Its parent is 5 >> 1 = 2 (binary 10). ans[5] = ans[2] + (5 & 1) = 1 + 1 = 2.
  • 4 in binary is 100. Its parent is 4 >> 1 = 2 (binary 10). ans[4] = ans[2] + (4 & 1) = 1 + 0 = 1.

Step-by-Step Explanation

Let's trace through with n = 5. We fill the dp array left to right using the recurrence ans[i] = ans[i >> 1] + (i & 1).

Step 1: Initialize ans[0] = 0. The number 0 has no set bits. This is our base case.

  • ans = [0, _, _, _, _, _]

Step 2: Compute ans[1].

  • Parent: 1 >> 1 = 0. ans[0] = 0.
  • Last bit: 1 & 1 = 1.
  • ans[1] = 0 + 1 = 1.
  • ans = [0, 1, _, _, _, _]

Step 3: Compute ans[2].

  • Parent: 2 >> 1 = 1. ans[1] = 1.
  • Last bit: 2 & 1 = 0 (2 is even).
  • ans[2] = 1 + 0 = 1.
  • ans = [0, 1, 1, _, _, _]

Step 4: Compute ans[3].

  • Parent: 3 >> 1 = 1. ans[1] = 1.
  • Last bit: 3 & 1 = 1 (3 is odd).
  • ans[3] = 1 + 1 = 2.
  • ans = [0, 1, 1, 2, _, _]

Step 5: Compute ans[4].

  • Parent: 4 >> 1 = 2. ans[2] = 1.
  • Last bit: 4 & 1 = 0 (4 is even).
  • ans[4] = 1 + 0 = 1.
  • ans = [0, 1, 1, 2, 1, _]

Step 6: Compute ans[5].

  • Parent: 5 >> 1 = 2. ans[2] = 1.
  • Last bit: 5 & 1 = 1 (5 is odd).
  • ans[5] = 1 + 1 = 2.
  • ans = [0, 1, 1, 2, 1, 2]

Result: [0, 1, 1, 2, 1, 2]

DP Right-Shift Recurrence — Building Answers from Previous Results — Watch how each number's set-bit count is derived from a previously computed result using the recurrence ans[i] = ans[i >> 1] + (i & 1).

Algorithm

  1. Create a result array ans of size n + 1, initialized to 0.
  2. For each number i from 1 to n:
    • Compute ans[i] = ans[i >> 1] + (i & 1).
    • i >> 1 is the parent (same number with last bit removed).
    • i & 1 tells us if the last bit is 1 (odd) or 0 (even).
  3. Return ans.

Code

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
};
class Solution:
    def countBits(self, n: int) -> list[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate from 1 to n exactly once. Each iteration performs a constant-time lookup (ans[i >> 1]), a bitwise AND, and an addition. No inner loops or recursive calls. Total work: exactly n iterations × O(1) each = O(n).

Space Complexity: O(1) (excluding the output array)

The only extra storage is the loop variable i. The output array ans is required by the problem specification, so it is not counted as auxiliary space. We achieve O(n) time with essentially zero extra memory.