Python solution with detailed explanation


  • 0
    G

    Solution

    Counting Bits https://leetcode.com/problems/counting-bits/

    Algorithm: n&(n-1) trick

    • First algorithm is to use the trick n & (n-1) which resets the lowest set bit to 0. Use this to count the number of set bits in each input number.
    class Solution(object):
        def count_ones(self, n):
            cnt = 0
            while n:
                n = n & (n-1)
                cnt += 1
            return cnt
        
        def countBits(self, num):
            """
            :type num: int
            :rtype: List[int]
            """
            result = []
            for i in range(num+1):
                result.append(self.count_ones(i))
            return result
    

    Dynamic programming

    class Solution(object):
        def countBits(self, num):
            """
            :type num: int
            :rtype: List[int]
            """
            result = [0]
            for i in range(1, num+1):
                result.append(result[i>>1] + int(i&1))
            return result
    

Log in to reply
 

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