@@ -0,0 +1,2196 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport org.junit.After;%0Aimport org.junit.Assert;%0Aimport org.junit.Before;%0Aimport org.junit.Test;%0A%0A/**%0A * Given a non negative integer number num. For every numbers i in the range 0 %E2%89%A4 i %E2%89%A4 num calculate the number of 1's in%0A * their binary representation and return them as an array.%0A * %3Cp%3E%0A * Example:%0A * For num = 5 you should return %5B0,1,1,2,1,2%5D.%0A * %3Cp%3E%0A * Follow up:%0A * %3Cp%3E%0A * It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n)%0A * /possibly in a single pass?%0A * Space complexity should be O(n).%0A * Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other%0A * language.%0A * Hint:%0A * %3Cp%3E%0A * You should make use of what you have produced already.%0A * Divide the numbers in ranges like %5B2-3%5D, %5B4-7%5D, %5B8-15%5D and so on. And try to generate new range from previous.%0A * Or does the odd/even status of the number help you in calculating the number of 1s?%0A * %3Cp%3E%0A * Tags: Dynamic Programming, Bit Manipulation%0A * Similar Problems: (E) Number of 1 Bits%0A */%0Apublic class CountingBits %7B%0A%0A    private CountingBits c;%0A%0A    /**%0A     * DP.%0A     * Recurrence Relation: f%5Bi%5D = f%5Bi / 2%5D + i %25 2.%0A     * It means that we can decompose the binary string of current integer into two parts:%0A     * 1) the rightmost bit%0A     * 2) from the second rightmost bit to the leftmost bit%0A     * For example: if i = 5, the binary string is 101, %2210%22 + %221%22%0A     * So the number of bits relates to the # of bits of i / 2, and whether it's odd or even.%0A     * If it's even, it has the same number of bits as %2210%22, which is 1.%0A     * If it's odd, it has one more, which is 2.%0A     */%0A    public int%5B%5D countBits(int num) %7B%0A        int%5B%5D res = new int%5Bnum + 1%5D;%0A        for (int i = 1; i %3C res.length; i++) %7B%0A            res%5Bi%5D = res%5Bi / 2%5D + i %25 2;%0A        %7D%0A        return res;%0A    %7D%0A%0A    @Before%0A    public void setUp() %7B%0A        c = new CountingBits();%0A    %7D%0A%0A    @Test%0A    public void testExamples() %7B%0A        Assert.assertArrayEquals(new int%5B%5D%7B0, 1, 1, 2, 1, 2%7D, c.countBits(5));%0A    %7D%0A%0A    @After%0A    public void tearDown() %7B%0A        c = null;%0A    %7D%0A%0A%7D%0A

add Counting Bits