Python One Line Solution


  • 3
    T

    First, it is easy to write up following codes:

    def memo(memsize):
        def m(f):
            r = [None] * memsize
            def g(n):
                if n >= memsize: return f(n)
                if n < memsize and r[n] != None: return r[n]
                r[n] = False
                r[n] = f(n)
                return r[n]
            return g
        return m
    
    @memo(256)
    def happy(n):
        if n == 1: return True
        n = sum([int(i) ** 2 for i in str(n)])
        return happy(n)
    
    class Solution:
        # @param {integer} n
        # @return {boolean}
        def isHappy(self, n):
            return happy(n)
    

    You may want to simplify it by using lookup table instead of memo with the result given by this code:

    class Solution:
        table = [i == '1' for i in '{:0250b}'.format(460375925594611245485020568205955132732929763215347324130389705269208163328L)]
        # @param {integer} n
        # @return {boolean}
        def isHappy(self, n):
            if n < 250: return self.table[n]
            return self.isHappy(sum([int(i) ** 2 for i in str(n)]))
    

    And, it is easy to test what circle may have at the end of iteration. Then, you will find out that it can only be:

    1 -> 1

    4 ->16 -> 26 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4

    Then, you may write codes like this:

    class Solution:
        # @param {integer} n
        # @return {boolean}
        def isHappy(self, n):
            return self.isHappy(sum([int(i) ** 2 for i in str(n)])) if n > 4 else n == 1
    

    After that, the code is simple and very easy.


  • 0

    Could you please explain what does '{:0250b}'.format(...) means?


  • 0
    S

    It is just a string representation for the memo from the first solution, if (250-n)th bit of the long number is 1, n is a happy number. You can get the number 460... checking happy numbers in range(1, 250):
    sol = Solution()
    res = 0
    for i in range(1, 250):
    res <<= 1
    if sol.isHappy(i):
    res += 1
    print res, '{:0250b}'.format(res)


Log in to reply
 

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