338. Counting Bits

Question

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

Constraints:

0 <= n <= 10<sup>5</sup>

---

Approach

1. Start checking numbers from 0 till n.
2. For every number, convert it into bits by doing % 2 and / 2, and if the result is 1, increment the count.
3. Append the count into the output vector.
4. Proceed to the next number.

Solution

class Solution {
public:
    vector<int> countBits(int n) {
        int i = 0;
        int count = 0;
        vector<int> res;
        
        while(i <= n){
            count = 0;
            int now = i;
            
            while(now >0){
                int rem = now % 2;
                now /= 2;
                if(rem == 1) count++;
            }
            
            res.push_back(count);
            i++;
        }
        return res;
    }
};