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.
1var countBits = function(n) {
2 let res = new Array(n + 1);
3 for (let i = 0; i <= n; i++) {
4 res[i] = i.toString(2).split('0').join('').length;
5 }
6 return res;
7};For JavaScript, we convert each number to its binary string using toString(2) and then count 1's by splitting and joining the string array without zeroes.
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.
1#include <vector>
2using namespace std;
3
4vector<int> countBits(int n) {
5 vector<int> res(n + 1, 0);
6 for (int i = 1; i <= n; ++i) {
7 res[i] = res[i >> 1] + (i & 1);
8 }
9 return res;
10}In C++, we utilize a vector to store the results. Each i's bit count is computed using the result of i/2 (right-shift) and adding 1 if i is odd.