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 <= 105Follow up:
O(n log n). Can you do it in linear time O(n) and possibly in a single pass?__builtin_popcount in C++)?The goal of #338 Counting Bits is to compute the number of set bits (1s) in the binary representation for every number from 0 to n. A naive approach would count bits for each number independently, but that leads to repeated work.
A more efficient strategy uses dynamic programming with bit manipulation. The key observation is that results for smaller numbers can help compute results for larger ones. For example, the number of set bits in a number can be derived from a previously computed value by removing the least significant bit or shifting the number right (i >> 1) and adjusting based on whether the last bit is 1.
This reuse of previously computed results allows us to build the answer iteratively from 0 to n. By storing intermediate results in an array, we avoid recomputation and achieve optimal efficiency. This approach runs in O(n) time with O(n) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Bit Manipulation | O(n) | O(n) |
| Naive Bit Counting for Each Number | O(n log n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You should make use of what you have produced already.
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
Or does the odd/even status of the number help you in calculating the number of 1s?
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.
Time Complexity: O(n log n) due to the division operations in each loop.
Space Complexity: O(n) for the result array.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int* countBits(int n, int* returnSizeThe function countBits allocates memory for the result array and initializes a loop to iterate over each number from 0 to n. Inside the loop, another while loop is used to count the number of 1's in the binary representation of the current number using bitwise AND and right shift operations.
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.
Time Complexity: O(n) due to a single loop.
Space Complexity: O(n) for the output array.
1var countBitsWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Counting Bits is a common interview problem because it tests understanding of bit manipulation and dynamic programming. Variations of this concept often appear in coding interviews at top tech companies.
The optimal approach uses dynamic programming combined with bit manipulation. By leveraging previously computed results, such as using i >> 1 or removing the lowest set bit, we can compute each value efficiently in linear time.
Dynamic programming helps avoid recalculating the number of set bits for every number from scratch. Instead, each result builds upon earlier results, significantly reducing redundant computation.
An array or list is typically used to store the number of set bits for every number from 0 to n. This allows previously computed results to be reused when calculating values for larger numbers.
In JavaScript, this function initializes an array and fills it using a formula based on the right shift for dividing numbers and bitwise AND for the last bit.