Python Simple Solution!!! Dynamic Programming


  • 0
    D

    Hi, guys may be my implementation will help. I just saw there was a clear pattern in the sequence.
    Let's say f(n) denotes the number of 1's in binary format of 'n'. Then, it follow this recursion

    f(n) = f(Reminder of n) + f ( Quotient of n ) 
    f(0) = 0 
    f(1) = 1
    

    The code is below, I am memozing in a defaultdict(). Hope it helps.

    class Solution(object):
    
        def countBits(self, num):
            temp_list = []
            self.out_dict = defaultdict()
            for i in xrange(num+1):
                temp_list+=[self.temp_count(i)]
    
            return temp_list
    
    
        def temp_count(self,num):
            if num == 0:
                return 0
            if num == 1:
                return 1
            if num in self.out_dict:
                return self.out_dict[num]
    
            self.out_dict[num] = self.temp_count(num % 2) + self.temp_count(num / 2)
            return self.out_dict[num]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.