Counting Bits - Leetcode Solution

Counting Bits is a problem on LeetCode that requires us to count the number of 1's in the binary representation of a given integer from 0 to n.

For example, if n=5, we need to count the number of 1's in binary representation of 0, 1, 2, 3, 4, and 5.

We can solve this problem using Dynamic Programming with Time complexity of O(n).

The Approach is to use the fact that the number of 1's in binary representation of a number i is equal to the number of 1's in binary representation of i/2 plus the last bit of i, which is 0 if i is even, and 1 if i is odd.

Algorithm:

1- Create an array dp of size n+1.

2- Initialize the first element dp[0] with 0.

3- Traverse through the range from 1 to n, and perform the following.

a) If the current number is even, then the number of 1's in its binary representation equals the number of 1's in i/2, which is stored in dp[i/2].

b) If the current number is odd, then the number of 1's in its binary representation equals the number of 1's in i/2 plus 1, which is stored in dp[i/2] + 1.

4- Assign the value of dp[i] equal to the above calculated value.

5- Return the array dp as solution.

Python Code:

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n+1)
        for i in range(1, n+1):
            if i%2 == 0:
                dp[i] = dp[i//2]
            else:
                dp[i] = dp[i//2] + 1
        return dp

C++ Code:

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n+1, 0);
        for(int i=1; i<=n; i++){
            if(i%2 == 0){
                dp[i] = dp[i/2];
            }
            else{
                dp[i] = dp[i/2] + 1;
            }
        }
        return dp;
    }
};

This gives us the required solution to the problem.

1