LeetCode 338. Counting Bits - Counting number of set bits in all numbers from 0 to num (Problem: https://leetcode.com/problems/counting-bits) - Given a non negative integer number num. For every number i in the range 0 ≤ i ≤ num, calculate and store the number of 1's in the binary representation of i and return results as an array. Example: For …

CountingBits.java

/**
 * LeetCode 338. Counting Bits
 * Counting number of set bits in all numbers from 0 to num (Problem Link: https://leetcode.com/problems/counting-bits)
 * Given a non negative integer number num. For every number i in the range 0 ≤ i ≤ num, calculate and store the number of 1's 
 * in the binary representation of i and return results as an array.
 * Example: For num = 5, program should return [0,1,1,2,1,2].
 */
 
public class CountingBits {
    
    static int countSetBits(int n){
        // Trick from K&R
        int count = 0;
        while(n != 0){
            n &= n-1;
            count++;
        }
        return count;
    }
    
    public int[] countBits(int num) {
        int[] result = new int[num+1];
        result[0] = 0; // No. of set bits in 0 is 0
        for(int i=1 ; i <= num; i++){
            if((i & (i - 1)) == 0){
                // All powers of 2 will have only 1 set bit
                result[i] = 1;
            }
            else{
                // Calculate set bits for all others
                result[i] = countSetBits(i);
            }
        }
        return result;
    }
}