DAY 90 - 338. Counting Bits

Hey Folks!. Welcome to day 90 of the 100DaysOfCode Challenge. We shall be covering Today's daily leetcode problem today.

Question: 338. Counting Bits

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

Intuition and Approach:

• The problem at hand asks us to count the number of 1's in the binary representation of integers from 0 to n . It's something that combines elements of DP and bitwise operations. The end result we want is an array which contains number of 1's for all integers from 0 to n.
• Okay we know what we want, but how do we get there.
• Let's look at individual things we can do, we know if we multiply something by 2 or shift it once we are shifting every bit by one and the incoming bit will be a 0.

• Hence if there was no set bit there means, the next number contains the same number of bits and if there was we can simply modulo the number with 2 and find it out.

• We got a relation: Number of set bits in a number is equal to number of bits set in it if it was halved + modulo(number%2).

Let's form a solution using this, but if we do this it will be highly inefficient. How about we use DP here and start from bottom answers we know that no of bits in 0 is 0 and no of bits in 1 is 1.

Approach:

• First, I initialize a vector called res of size n+1 to store the count of set bits (1s) for numbers from 0 to n. Since there are no set bits in the binary representation of 0, I set res[0] to 0.
• Then, I use a loop to iterate from 1 to n. For each number i in this range, I calculate the count of set bits in its binary representation. I do this by taking advantage of the fact that the binary representation of i is formed by shifting the binary representation of i >> 1 one position to the right and adding i % 2 as the last bit. This effectively counts the number of set bits in i based on the count in the binary representation of i >> 1.
• Finally, I return the res vector, which contains the count of set bits for all numbers from 0 to n.

Code:

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n+1);

        //dp
        res[0] = 0;

        for(int i = 1;  i <=n; ++i){
            res[i] = res[i >> 1] + i%2;
        }

        return res;
    }
};

Complexity Analysis: