2.Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:
Input: 2
Output: [0,1,1]

Example 2:
Input: 5
Output: [0,1,1,2,1,2]

Solution I : (Using STL)

class Solution
{
public:
    vector<int> countBits(int num)
    {

        vector<int> v;
        for (int i = 0; i <= num; i++)
        {
            bitset<32> b(i);
            int x = b.count();
            v.push_back(x);
        }
        return v;
    }
};

Solution II:(Brian Kernighan’s Algorithm)

class Solution
{
public:
    int countB(int n)
    {

        int count = 0;
        while (n != 0)
        {

            n = n & (n - 1);
            count++;
        }
        return count;
    }
    vector<int> countBits(int num)
    {
        vector<int> v;
        for (int i = 0; i <= num; i++)
        {
            int x = countB(i);
            v.push_back(x);
        }
        return v;
    }
};

Time Complexity: O(n log n)

Solution III: (Using property of even odd no and division)

Algorithm: If i is even then it will have the same number of set bits as i / 2 because to get the number i we just shift the LSB in i / 2 by one. While shifting, the number of set bits in i/2 does not change. If i is odd then dividing the number means doing 1 right shift and here 1 set bit will be lost. So the number i/2 will have 1 set bit less than the original number.

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

Time Complexity: O(n) , Space Complexity:O(n)