# 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)

```cpp
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**)

```cpp
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:** \
&#x20;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.**

```cpp
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)**