Counting Bits

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

Example:

Input:  5
Output: {0,1,1,2,1,2}

Approach

Java

import java.util.Arrays;

public class CountingBits {
    public static void main(String[] args) {
        int n = 5;
        int bits[] = countBits(n);
        System.out.println(Arrays.toString(bits));
    }

    static int[] countBits(int num) {
        int res[] = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            int j = i;
            int cnt = 0;
            while (j > 0) {
                if (j % 2 != 0)
                    cnt++;
                j = j >> 1;
            }
            res[i] = cnt;
        }
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> countBits(int num)
{
        vector<int> res;
        for(int i=0;i<=num;i++)
        {
            int j=i;
            int cnt=0;
            while(j)
            {
                if(j&1)
                    cnt++;
                j=j>>1;
            }
            res.push_back(cnt);
        }
        return res;
}
int main()
{
    int n=5;
    vector<int> bits=countBits(n);
    for(int i=0;i<bits.size();i++)
       cout<<bits[i]<<" ";
    return 0;
}