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* returnSize) {
6 *returnSize = n + 1;
7 int* res = (int*)malloc(sizeof(int) * (*returnSize));
8 for (int i = 0; i <= n; ++i) {
9 int count = 0;
10 int num = i;
11 while (num) {
12 count += num & 1;
13 num >>= 1;
14 }
15 res[i] = count;
16 }
17 return res;
18}The 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.
1def countBits(n):
2 res = [0] * (n + 1)
3 for i in range(1, n + 1):
4 res[i] = res[i >> 1] + (i & 1)
5 return resThis Python solution creates a list initialized to zero and uses a loop to fill each position using the count from the bit-shifted index plus the last bit.