1
class Solution:
2
    def isSquare(self, n: int) -> bool:
3
        sq = int(math.sqrt(n))
4
        return sq * sq == n
5

6
    def numSquares(self, n: int) -> int:
7
        # Lagrange's four-square theorem
8
        if self.isSquare(n):
9
            return 1
10
        while (n & 3) == 0:
11
            n >>= 2
12
        if (n & 7) == 7:
13
            return 4
14
        sq = int(math.sqrt(n)) + 1
15
        for i in range(1, sq):
16
            if self.isSquare(n - i * i):
17
                return 2
18
        return 3