Solution For Counting Bits

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.

Step by Step Implementation For Counting Bits

public class Solution {
    public int[] countBits(int num) {
        
        // create an array to store the number of bits for each number from 0 to num
        int[] result = new int[num + 1];
        
        // for each number from 0 to num
        for (int i = 0; i <= num; i++) {
            
            // initialize the number of bits to 0
            int bits = 0;
            
            // create a variable to store the current number
            int n = i;
            
            // while the current number is greater than 0
            while (n > 0) {
                
                // if the rightmost bit is 1
                if ((n & 1) == 1) {
                    
                    // increment the number of bits
                    bits++;
                }
                
                // right shift the current number
                n = n >> 1;
            }
            
            // store the number of bits in the array
            result[i] = bits;
        }
        
        // return the array
        return result;
    }
}

class Solution:
    def countBits(self, num: int) -> List[int]:
        # create an empty list to store the results
        results = []
        
        # loop through each number from 0 to num
        for i in range(num+1):
            # convert the number to binary
            binary = bin(i)[2:]
            # count the number of ones in the binary representation
            count = binary.count("1")
            # append the count to the results list
            results.append(count)
            
        # return the results list
        return results

var countBits = function(num) {
    
    // create an empty array to store the results
    let results = [];
    
    // loop through each number from 0 to num
    for (let i = 0; i <= num; i++) {
        
        // convert the number to binary
        let binary = i.toString(2);
        
        // count the number of ones in the binary representation
        let ones = 0;
        for (let j = 0; j < binary.length; j++) {
            if (binary[j] === "1") {
                ones++;
            }
        }
        
        // add the number of ones to the results array
        results.push(ones);
    }
    
    // return the results array
    return results;
};

class Solution {
public:
    vector countBits(int num) {
        vector res(num+1, 0);
        for(int i=1; i<=num; i++)
            res[i] = res[i/2] + (i&1);
        return res;
    }
};

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

// This solution uses the fact that the number of 1 bits in a number is equal to the number of 1 bits in half the number, plus 1 if the number is odd.