338. Counting Bits

Description:

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.

 

/*
[1] naive solution)

idea::
from 0 to n, count all of the number of 1 bits

code::

countingBits(int n) -> return 1bits number, using 1 mask

int[] ans=new int[n+1];
for(int i=0;i<=n;++i){
    ans[i]=countingBits(i);
}
return ans;

-T/C: O(32*n)
-S/C: O(n+1) #it contains ans size
*/
/*
[2] efficient solution)

idea::
using n&(n-1), count the number of 1 bit from right side of num in binary presentation

code::
(below)

-T/C: O(k*n),  k== the number of 1 bits
-S/C: O(n+1)
*/
    


class Solution {
    public int[] countBits(int n) {
        int[] ans=new int[n+1];
        for(int i=0;i<=n;++i){
            ans[i]=counting(i);
        }
        return ans;
    }
    
    public int counting(int n){
        int count=0;
        while(n>0){
            n=n&(n-1);
            ++count;
        }
        return count;
    }
}