1. Description

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

2. Runtime Distribution

3. Submission Details

4. Example

For num = 5 you should return [0,1,1,2,1,2].

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public int[] countBits(int num)
{
    int[] res = new int[num + 1];
    for (int i = 1; i <= num; i++) {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
}

[/restab]
[restab title="Java"]

public int[] countBits(int num)
{
    int[] results = new int[num + 1];
    for (int i = 0; i <= num; i++) {
        results[i] = bitCount(i);
    }
    return results;
}

private int bitCount(int number)
{
    int count = 0;
    while (number != 0) {
        count++;
        number = (number - 1) & number;
    }
    return count;
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

public class LeetCode0338 {
    public int[] countBits(int num)
    {
        int[] res = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }

    public static void main(String[] args)
    {
        LeetCode0038 leetcode = new LeetCode0038();
        int[] results = leetcode.countBits(5);
        for (int result : results) {
            System.out.println(result);
        }
    }
}

[/restab]
[restab title="Java"]

public class LeetCode0338 {
    public int[] countBits(int num)
    {
        int[] results = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            results[i] = bitCount(i);
        }
        return results;
    }

    private int bitCount(int number)
    {
        int count = 0;
        while (number != 0) {
            count++;
            number = (number - 1) & number;
        }
        return count;
    }

    public static void main(String[] args)
    {
        LeetCode0338 leetcode = new LeetCode0338();
        int[] results = leetcode.countBits(5);
        for (int result : results) {
            System.out.println(result);
        }
    }
}

[/restab]
[/restabs]