54 ms Python solution, what can be improved?


  • 3
    C
    class Solution:
        # @param n, an integer
        # @return an integer
        def hammingWeight(self, n):
            count=0
            m=str(bin(n))
            for i in m:
                if i=='1':
                    count+=1
            return count
    

    This is an O(n) solution I believe. Is there any way to speed it up?


  • 1
    S
    class Solution:
        # @param n, an integer
        # @return an integer
        def hammingWeight(self, n):
            count = 0
            i = 31
            while i >= 0:
                if n > 2 ** i:
                    n = n - 2 ** i
                    count = count + 1
                elif n == 2 ** i:
                    count = count + 1
                    break
                i = i - 1
            return count
    

    58ms 无脑Code


  • 2
    W
    class Solution:
        # @param n, an integer
        # @return an integer
        def hammingWeight(self, n):
            return len([char for char in bin(n) if char=='1'])
    

    also 54ms.but i think it is more consice


  • 2
    P
    class Solution:
        # @param n, an integer
        # @return an integer
        def hammingWeight(self, n):
            cnt = 0
            while n > 0:
                cnt += 1
                n &= n-1
            return cnt
    

    48 ms but still O(n) if there are only ones in the number


  • 0
    M

    nice ! mine is a one-liner solution too . I ended up using zfill to make it a 32 bit integer and then counted the number of 1's.


  • 0
    W

    If you change 'for i in m:' to 'for i in m[2:]:', you can AC in 52ms...

    Personally, I don't think this thought can speed it up to 10 or 20ms, it is not really.


Log in to reply
 

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