Day 6 Leet code series, today we will be picking the problem Counting bits (https://leetcode.com/problems/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

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res;
        for(int i=0;i<=n;i++){
            res.push_back(countSetBits(i));
        }
        return res;
    }
    
    int countSetBits(int n){
        int count = 0;
        for(int i=0; i<=31;i++){
            if((n & (1 << i)) > 0){
                count++;
            }
        }
        return count;
    }
};

Explaination:

1. We will be using bits manipulation to solve this problem
2. num & (1 << i) which is used here. 1<<i which means setting the i th bit. Suppose i is 3 then 1 left shift 3 is 100, and bitwise & with num will give use the bit. If they are set then we do count++.