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 <vector>
2using namespace std;
3
4vector<int> countBits(int n) {
5 vector<int> res(n + 1, 0);
6 for (int i = 0; i <= n; ++i) {
7 res[i] = __builtin_popcount(i);
8 }
9 return res;
10}This C++ solution uses the built-in function __builtin_popcount to count the number of 1's in each integer's binary form. We compute this for each number from 0 to n and store the result in a vector.
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 <stdio.h>
2#include <stdlib.h>
3
4int* countBits(int n, int* returnSize) {
5 *returnSize = n + 1;
6 int* res = (int*)malloc(sizeof(int) * (*returnSize));
7 res[0] = 0;
8 for (int i = 1; i <= n; ++i) {
9 res[i] = res[i >> 1] + (i & 1);
10 }
11 return res;
12}The function initializes the result array with the base case of zero bits for zero. For each i from 1 to n, it calculates the number of 1's as the sum of bits in i/2 and the last bit of i using bitwise operations.