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.
1import java.util.*;
2
3public class Solution {
4 public int[] countBits(int n) {
5 int[] res = new int[n + 1];
6 for (int i = 0; i <= n; i++) {
7 res[i] = Integer.bitCount(i);
8 }
9 return res;
10 }
11}In this Java solution, Integer.bitCount is used to count the number of 1's in the binary representation of each number from 0 to n. The result is stored in an integer array.
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.