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.

Description Hints 3 Solution Video 13:24

338. Counting Bits

Easy80.5% acceptance9 companies

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++)?