338. Counting Bits - Solution & Explanation

The problem

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.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

0 <= n <= 10⁵

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Approach overview

Problem Overview: Given an integer n, return an array ans where ans[i] represents the number of 1 bits in the binary representation of i for every number from 0 to n. The challenge is computing all counts efficiently instead of recalculating bits for each number independently.

Approach 1: Naïve Count Bits Approach (O(n log n) time, O(1) extra space)

The straightforward approach processes each integer from 0 to n and counts the set bits in its binary representation. You repeatedly divide the number by two (right shift) and increment a counter whenever the least significant bit is 1. Another variation uses Brian Kernighan’s trick (x = x & (x - 1)) to remove the lowest set bit until the number becomes zero. This approach is simple and demonstrates understanding of bit manipulation, but each number may take up to O(log n) operations to process. Overall complexity becomes O(n log n). It works fine for small inputs but does redundant work because adjacent numbers share overlapping binary patterns.

Approach 2: Dynamic Programming with Bit Relation (O(n) time, O(n) space)

The optimal solution uses a recurrence relationship between numbers. Observe that shifting a number right removes its least significant bit. The count of set bits for i can be derived from a smaller number: dp[i] = dp[i >> 1] + (i & 1). The expression i >> 1 removes the last bit, while (i & 1) checks whether that removed bit was 1. Since dp[i >> 1] has already been computed earlier, you reuse previously calculated results instead of recomputing the entire bit count.

This creates a bottom‑up dynamic programming solution. Start with dp[0] = 0. Iterate from 1 to n, applying the recurrence. Each step performs constant-time bit operations, producing an overall time complexity of O(n) with O(n) space for the result array.

Another equivalent recurrence uses the expression dp[i] = dp[i & (i - 1)] + 1. The operation i & (i - 1) removes the lowest set bit from i. Since that smaller value already has its bit count stored, you simply add one. Both formulas rely on properties of bit manipulation and reuse computed results, which is the core idea behind dynamic programming.

Recommended for interviews: Interviewers expect the dynamic programming solution with O(n) time. Starting with the naïve bit counting approach shows basic understanding of binary operations. Moving to the recurrence relation demonstrates optimization skills and recognition of overlapping subproblems, which is exactly what the question is designed to test.

Approach 1: Naïve Count Bits Approach

This approach involves converting each number to its binary representation and counting the number of 1's in this binary form. We'll iterate through each number from 0 to n, convert the number to its binary form using standard built-in methods, and then count the number of 1's using another built-in method or implement a small function for counting.

Python

def countBits(n):
    return [bin(i).count('1') for i in range(n + 1)]

Java

import java.util.*;

public class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = Integer.bitCount(i);
        }
        return res;
    }
}

C++

#include <vector>
using namespace std;

vector<int> countBits(int n) {
    vector<int> res(n + 1, 0);
    for (int i = 0; i <= n; ++i) {
        res[i] = __builtin_popcount(i);
    }
    return res;
}

JavaScript

var countBits = function(n) {
    let res = new Array(n + 1);
    for (let i = 0; i <= n; i++) {
        res[i] = i.toString(2).split('0').join('').length;
    }
    return res;
};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* countBits(int n, int* returnSize) {
    *returnSize = n + 1;
    int* res = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i <= n; ++i) {
        int count = 0;
        int num = i;
        while (num) {
            count += num & 1;
            num >>= 1;
        }
        res[i] = count;
    }
    return res;
}

public class Solution {
    public int[] CountBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = CountOnes(i);
        }
        return res;
    }
    private int CountOnes(int num) {
        int count = 0;
        while (num > 0) {
            count += num & 1;
            num >>= 1;
        }
        return count;
    }
}

In this Python solution, a list comprehension is used to generate the result. The bin function converts the number to a binary string and the count method counts the number of 1's.

Complexity

Time Complexity: O(n log n) due to conversion and counting.
Space Complexity: O(n) for the list storage.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

This optimized approach utilizes dynamic programming. The key observation is that for a number i, the number of 1's is equal to the number of 1's in i/2 plus i mod 2. This allows us to build the array progressively and with linear time complexity.

Python

def countBits(n):
    res = [0] * (n + 1)
    for i in range(1, n + 1):
        res[i] = res[i >> 1] + (i & 1)
    return res

Java

import java.util.*;

public class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for (int i = 1; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}

C++

#include <vector>
using namespace std;

vector<int> countBits(int n) {
    vector<int> res(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
}

JavaScript

var countBits = function(n) {
    let res = new Array(n + 1);
    res[0] = 0;
    for (let i = 1; i <= n; i++) {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
};

#include <stdio.h>
#include <stdlib.h>

int* countBits(int n, int* returnSize) {
    *returnSize = n + 1;
    int* res = (int*)malloc(sizeof(int) * (*returnSize));
    res[0] = 0;
    for (int i = 1; i <= n; ++i) {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
}

public class Solution {
    public int[] CountBits(int n) {
        int[] res = new int[n+1];
        for (int i = 1; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}

This Python solution creates a list initialized to zero and uses a loop to fill each position using the count from the bit-shifted index plus the last bit.

Complexity

Time Complexity: O(n) due to loop through each number.
Space Complexity: O(n) for the array space.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function countBits(n: number): number[] {
    const ans: number[] = Array(n + 1).fill(0);
    for (let i = 0; i <= n; ++i) {
        ans[i] = bitCount(i);
    }
    return ans;
}

function bitCount(n: number): number {
    let count = 0;
    while (n) {
        n &= n - 1;
        ++count;
    }
    return count;
}

func countBits(n int) []int {
	ans := make([]int, n+1)
	for i := 0; i <= n; i++ {
		ans[i] = bits.OnesCount(uint(i))
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Naïve Count Bits Approach	Time Complexity: O(n log n) due to conversion and counting. Space Complexity: O(n) for the list storage.
Dynamic Programming Approach	Time Complexity: O(n) due to loop through each number. Space Complexity: O(n) for the array space.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Naïve Count Bits	O(n log n)	O(1)	Good for understanding basic bit counting or when implementing a quick brute-force solution
Dynamic Programming with Bit Relation	O(n)	O(n)	Best choice for interviews and large inputs since each number is computed using previously calculated results

Frequently asked questions

Is Counting Bits easy or hard?

Counting Bits is classified as an Easy problem on LeetCode. The brute-force idea is simple, but recognizing the dynamic programming relationship that reduces the complexity to O(n) is the key insight interviewers look for.

How to solve Counting Bits in O(n)?

Use a dynamic programming recurrence. For each number i, compute dp[i] = dp[i >> 1] + (i & 1). The right shift removes the last bit while (i & 1) determines whether the removed bit was 1. Since dp[i >> 1] is already known, each step takes constant time.

What is the best approach for Counting Bits?

The dynamic programming approach using the relation dp[i] = dp[i >> 1] + (i & 1) is the most efficient. It computes the number of set bits for each number from 0 to n using previously calculated results. This reduces the time complexity to O(n) with O(n) space.

What data structure is used in Counting Bits?

The solution primarily uses an array (or list) to store results for all values from 0 to n. This array acts as the dynamic programming table where each index represents the number and the stored value represents its bit count.

What is the time complexity of Counting Bits?

The optimal dynamic programming solution runs in O(n) time because each integer from 1 to n is processed exactly once with constant-time bit operations. The naïve method that counts bits individually takes O(n log n) time since each number may require up to log n bit checks.

Counting Bits Python or Java solution approach?

Both Python and Java implementations follow the same DP formula: dp[i] = dp[i >> 1] + (i & 1). Initialize an array of size n + 1, iterate from 1 to n, and fill each position using the recurrence. The logic remains identical across languages.

Is Counting Bits asked at Google, Amazon, or Meta?

Counting Bits is a common bit manipulation and dynamic programming interview problem that appears in coding interviews at large tech companies. Variations of this problem have been reported in interviews at companies like Google, Amazon, and Microsoft because it tests understanding of binary operations and DP optimization.

Counting Bits solution and explanation

The problem

Approach overview

Approach 1: Naïve Count Bits Approach

Approach 2: Dynamic Programming Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Counting Bits solution and explanation

The problem

Approach overview

Approach 1: Naïve Count Bits Approach

Approach 2: Dynamic Programming Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems