Counting Bits
Problem Description
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:
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
Constraints:
- 0 <= n <= 105
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 timeO(n)and possibly in a single pass? - Can you do it without using any built-in function (i.e., like
__builtin_popcountin C++)?
Solve it on LeetCode
Approaches
1. Naive Approach
Intuition:
The naive approach involves iterating over each number from 0 to n and calculating the number of 1's in its binary representation. This can be achieved by repeatedly dividing the number by 2 and counting the remainder when divided by 2.
Code:
- Time Complexity: O(n * log(n)) because for each number up to n, we are performing shifts proportional to log(n).
- Space Complexity: O(n) for the output array.
2. DP with Last Significant Bit
Intuition:
A powerful way to compute the number of 1-bits for all numbers from 0 to n is to use a simple observation about binary numbers:
For any number i:
- Right shift (
i >> 1) removes the last bit. This meansi >> 1is simplyi / 2(integer division). Soi >> 1has the same bits asiexcept for the least significant bit. i & 1extracts the last bit ofi.- If it's odd → last bit is 1 → contributes +1
- If it's even → last bit is 0 → contributes +0
This allows us to build the result using previously computed values, making the solution both efficient and elegant.
Instead of counting bits from scratch for every number, we reuse the results from smaller numbers.
Code:
- Time Complexity: O(n) because we compute the number of bits for each number up to n exactly once.
- Space Complexity: O(n) for the output array.
Example Walkthrough:
Let’s compute res[0..7]
res[0] = 0i = 1→res[1] = res[0] + 1 = 1i = 2→res[2] = res[1] + 0 = 1i = 3→res[3] = res[1] + 1 = 2i = 4→res[4] = res[2] + 0 = 1i = 5→res[5] = res[2] + 1 = 2i = 6→res[6] = res[3] + 0 = 2i = 7→res[7] = res[3] + 1 = 3
3. Powers of two
Intuition:
This approach relies on understanding how binary representations behave around powers of two.
For any number x, if it lies in the interval: 2^m ≤ x < 2^(m+1)
then we can express it as: x = 2^m + k where 0 ≤ k < 2^m
What does this mean in terms of set bits?
2^mhas exactly one 1-bit, and it appears at position m.- The remaining part,
k, contains whatever lower bits x has.
So the number of 1-bits in x becomes:
This allows us to reuse previously computed results from the range [0 … 2^m − 1].
We simply identify the most recent power of two, subtract it from x to get k, and use:
Code:
- Time Complexity: O(n) because we are iterating over each element only once.
- Space Complexity: O(n) for the output array.