leetcode

Perfect Squares

Perfect Squares

Binary Search Version - 356ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math
class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        s = [i*i for i in range(1,int(math.sqrt(n))+1)] # Square numbers <= n
        l = 0  # BFS level
        currentLevel = [0]  # List of numbers in BFS level l
        while True:
            nextLevel = []
            for a in currentLevel:
                for b in s:
                    if a+b == n: return l+1  # Found n
                    if a+b < n:  nextLevel.append(a+b)
            currentLevel = list(set(nextLevel))  # Remove duplicates
            l += 1

test code

1
2
In [315]: s = Solution(); t = s.numSquares(11); print(t)
3

leet code