Python using four square theorem


  • 0
    W
    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            sq=[]
            i=1
            while i*i<=n:
                sq.append(i*i)
                i+=1
            if n in sq:
                return 1
            else:
                for x in sq:
                    if n-x in sq:
                        return 2
            sq2=[]
            for x in sq:
                for y in sq:
                    sq2.append(x+y)
            for x in sq:
                if n-x in sq2:
                    return 3
            return 4

Log in to reply
 

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