Leetcode: Perfect Squares

Perfect Squares



Similar Problems:


Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/perfect-squares
## Basic Ideas: BFS. Find the mininum steps
##              Get a list of square numbers as the candidate to explore
##
## Complexity: Time O(n*n), Space O(n)
class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        square_list = []
        i = 1
        while i*i <= n:
            if i*i == n: return 1
            square_list.append(i*i)
            i += 1

        level = 0
        queue = set([n])

        while len(queue) != 0:
            level += 1
            # use set, since we will have duplicate numbers to check
            s = set([])
            for num in queue:
                for square in square_list:
                    new_val = num - square
                    if new_val == 0: return level
                    # The follow values won't fix
                    if new_val < 0: break
                    # next candidate
                    s.add(new_val)
            queue = s

        # we shouldn't go to this line
        return None

# s = Solution()
# print(s.numSquares(12)) # 3
# print(s.numSquares(7168)) # 4
# print(s.numSquares(1103))
# print(s.numSquares(5756))
# print(s.numSquares(6255))
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.