Counting Bits

easy
Bit ManipulationDynamic ProgrammingBit Manipulation

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of set bits (1s) in the binary representation of i, for each i from 0 to n.

Examples

Example 1

  • Input: n = 2
  • Output: [0,1,1]
  • Explanation: 0 has 0 set bits, 1 has 1 set bit, 2 has 1 set bit.

Example 2

  • Input: n = 5
  • Output: [0,1,1,2,1,2]
  • Explanation: The binary representations are 0=0, 1=1, 10=1, 11=2, 100=1, 101=2.

Constraints

  • 0 <= n <= 10^5

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Pop Count for Each Number

Intuition

The most direct approach is to compute the number of set bits for each integer from 0 to n individually. For each number, we can use Brian Kernighan's trick (i & (i - 1) removes the lowest set bit) to count bits efficiently. While this approach is straightforward, it does not leverage the relationship between numbers, so it does redundant work across iterations.

Algorithm

  1. Create a result array of size `n + 1`.
  2. For each integer `i` from `0` to `n`, count the number of set bits using a loop with `i & (i - 1)`.
  3. Store the count in `result[i]`.
  4. Return the result array.
TimeO(n * k) where k is the average number of set bits per numberSpaceO(n) for the output array

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1);
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int x = i;
            while (x != 0) {
                x &= (x - 1);
                count++;
            }
            ans[i] = count;
        }
        return ans;
    }
};
Java 21
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int x = i;
            while (x != 0) {
                x &= (x - 1);
                count++;
            }
            ans[i] = count;
        }
        return ans;
    }
}
Python 3.12
from typing import List


class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(n + 1):
            count = 0
            x = i
            while x:
                x &= x - 1
                count += 1
            ans[i] = count
        return ans
Go 1.26
func countBits(n int) []int {
    ans := make([]int, n+1)
    for i := 0; i <= n; i++ {
        count := 0
        x := i
        for x != 0 {
            x &= x - 1
            count++
        }
        ans[i] = count
    }
    return ans
}
Approach 2

Dynamic Programming with Last Set Bit

Intuition

We can solve this in O(n) time by using the relationship countBits(i) = countBits(i & (i - 1)) + 1. The expression i & (i - 1) removes the lowest set bit from i, giving a smaller number whose answer we have already computed. Since removing one set bit means the count decreases by exactly one, we simply look up the previously computed value and add one. This avoids recomputing bit counts from scratch.

Algorithm

  1. Create a result array of size `n + 1`, initialized to zero.
  2. For each integer `i` from `1` to `n`, set `ans[i] = ans[i & (i - 1)] + 1`.
  3. Return the result array.
TimeO(n)SpaceO(n) for the output array

Code (C++ · Java · Python · Go)

C++17
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 & (i - 1)] + 1;
        }
        return ans;
    }
};
Java 21
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i & (i - 1)] + 1;
        }
        return ans;
    }
}
Python 3.12
from typing import List


class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i & (i - 1)] + 1
        return ans
Go 1.26
func countBits(n int) []int {
    ans := make([]int, n+1)
    for i := 1; i <= n; i++ {
        ans[i] = ans[i&(i-1)] + 1
    }
    return ans
}

Frequently asked questions

What is the optimal time complexity of Counting Bits?

The most efficient approach in this guide ("Dynamic Programming with Last Set Bit") runs in O(n) time and uses O(n) for the output array extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Counting Bits use?

Counting Bits is a easy-level Bit Manipulation problem involving Dynamic Programming, Bit Manipulation. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Counting Bits be solved without extra space?

The most space-efficient approach in this guide uses O(n) for the output array extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the output array, while the optimized version uses O(n) for the output array.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Number of 1 Bits

Original problem: leetcode.com

Loading editor...
Input
n=
0
Expected Output
[0]