#!/usr/bin/env python
# coding: utf-8

# <h1>Counting Bits</h1>
# <hr>
# 
# <!--Copy Paste Leetcode statement between-->
# <p>Given a non negative integer number <b>num</b>. For every numbers <b>i</b> in the range <b>0 ≤ i ≤ num</b> calculate the number of 1's in their binary representation and return them as an array.</p>
# 
# <p><strong>Example 1:</strong></p>
# 
# <pre><strong>Input: </strong><span id="example-input-1-1">2</span>
# <strong>Output: </strong><span id="example-output-1">[0,1,1]</span></pre>
# 
# <p><strong>Example 2:</strong></p>
# 
# <pre><strong>Input: </strong><span id="example-input-1-1">5</span>
# <strong>Output: </strong><code>[0,1,1,2,1,2]</code>
# </pre>
# <!--Copy Paste Leetcode statement between-->
# 
# <p>&nbsp;</p>
# <a href="https://leetcode.com/problems/counting-bits/">Source</a> 
# <hr>

# <h4>Code</h4>

# In[9]:


def count_bits(num):
    """Naive answer. Really slow"""
    res = []
    for i in range(0, num+1):
        res.append(sum(int(char) for char in '{:064b}'.format(i)))
    return res


# <h4>Check</h4>

# In[23]:


count_bits(2)


# In[24]:


count_bits(5)


# In[25]:


count_bits(25)


# <hr>
# <h4>Follow up:</h4>
# <p>It is very easy to come up with a solution with run time <b>O(n*sizeof(integer))</b>. But can you do it with the following constraints:</p>
# <ul>
# 	<li>Linear time <b>O(n)</b> /possibly in a single pass?</li>
# 	<li>Space complexity should be <b>O(n)</b>.</li>
# 	<li>Can you do it without using any builtin function like <b>__builtin_popcount</b> in c++ or in any other language.</li>
# </ul>
# 
# 
# <h4>Code</h4>

# In[ ]:


def count_bits(num):
    """Dynamic Programming: 

    case 1: n is even
        --> finishes with 0
        --> removing last binary digit wouldnt change number of 1
        --> f(num) = f(num >> 1) = f(num/2)

    case 1: n is odd number
        --> finishes with 1
        --> we can pluck it and add 1
        --> f(num) = 1 + f(num >> 1) = 1 + f(num/2)
    """
    result = [0]
    for i in range(1, num+1):
    
        # Option 1
        d, m = divmod(i,2)
        result.append(result[d] + m)
    
        # Option 2:
        # result.append(result[i >> 1] + (i & 1))  # i&1 = 0 if even, 1 if odd

    return result


# In[ ]:


def count_bits(num):
    """Using the following bit manipulation trick (Brian Kernighan's Algorithm):
     n & (n-1)    --> removes rightmost setbit:
    37 & 36 = 36  -->   100101 & 100100 = 100100
    36 & 35 = 32  -->   100100 & 100000 = 100000
    32 & 31 = 0   -->   100000 & 011111 = 000000
    
    
    Subtracting 1 = flips all the bits after the rightmost set bit (including rightmost bit)
    10: 000010|10       9: 0000100|1        8: 0000|1000      7: 0000011|1
     9: 000010|01       8: 0000100|0        7: 0000|0111      6: 0000011|0
    """
    def kernighan_algo(n):
        """Time Complexity O(k) with k number of setbits (as opposed to O(n))"""
        count = 0
        while (n):
            n = n & (n-1)
            count = count + 1
        return count
    
    result = [0]
    for i in range(1, num+1):
        nb_setbit = kernighan_algo(i)
        result.append(nb_setbit)
    return result


# In[ ]:


def count_bits(num):
    """One liner version of above solution
    """
    result = [0]
    for i in range(1, num+1):
        result.append(result[i & (i-1)] + 1)
    return result