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.
1def countBits(n):
2 return [bin(i).count('1') for i in range(n + 1)]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.
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 countBits = function(n) {
2 let res = new Array(n + 1);
3 res[0] = 0;
4 for (let i = 1; i <= n; i++) {
5 res[i] = res[i >> 1] + (i & 1);
6 }
7 return res;
8};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.