Binary Bits Count II

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
 

Constraints:

0 <= n <= 105

Solution

public class Solution {
    public int[] CountBits(int n) {
        
        var result = new int[n+1];
        for(int i=0;i<=n;i++)
        {
            int num=i;
            int count = 0;
            while (num != 0) {
                 count += (int)(num & 1);
                 num >>= 1;
            }
            result[i]=count;
        }
        return result;
    }
}

The time complexity of the algorithm is O(n log m), where n is the input to the function and m is the maximum number in the range from 0 to n. This is because there are n numbers in the range, and for each number, we’re counting the number of ‘1’ bits, which takes log(m) time in the worst case.

The space complexity of the algorithm is O(n), which means it uses a linear amount of space. This is because we’re creating an array result of size n+1 to store the bit counts for all numbers from 0 to n. The size of this array grows linearly with the size of the input.