# Perfect Squares

MathDPDFS

## # Import

from math import sqrt

1

## # Solution

TLE

### # Brute Force

Exponential runtime. TLE on 55.

def numSquares(self, n: int) -> int:
square_nums = [i**2 for i in range(1, int(sqrt(n))+1)]

def minNumSquares(k: int) -> int:
if k in square_nums:
return 1
min_num = sys.maxsize
# find the minimal value among all possible solutions
for square in square_nums:
if k < square:
break
min_num = min(min_num, minNumSquares(k-square) + 1)
return min_num

return minNumSquares(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

### # Memoized DP - Top Down

def numSquares(self, n: int) -> int:
square_nums = [i**2 for i in range(1, int(sqrt(n))+1)]
memo = [sys.maxsize for _ in range(n+1)]
memo[0] = 0

def minNumSquares(k: int) -> int:
if k in square_nums:
memo[k] = 1
if memo[k] < sys.maxsize:
return memo[k]
# find the minimal value among all possible solutions
for square in square_nums:
if k < square:
break
memo[k] = min(memo[k], minNumSquares(k-square) + 1)
return memo[k]

return minNumSquares(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

### # Memoized DP - Bottom Up

$\text{numSquares}(n) = \min \Big(\text{numSquares(n-k) + 1}\Big) \qquad \forall k \in {\text{square numbers}}$

Complexity

time: $O(n\cdot\sqrt{n})$
space: $O(n)$

def numSquares(self, n: int) -> int:
square_nums = [i**2 for i in range(1, int(sqrt(n))+1)]
dp = [sys.maxsize for _ in range(n+1)]
dp[0] = 0

for i in range(1, n+1):
for square in square_nums:
if i < square:
break
dp[i] = min(dp[i], dp[i-square] + 1)

return dp[-1]

1
2
3
4
5
6
7
8
9
10
11
12

### # Greedy Enumeration

Complexity

time: $O(\frac{\sqrt{n}^{h+1} - 1}{\sqrt{n}-1}) = O(n^{\frac{h}{2}})$
space: $O(\sqrt{n})$

def numSquares(self, n: int) -> int:
square_nums = set(i**2 for i in range(1, int(sqrt(n))+1))

def is_divided_by(n, cnt):
"""
return: true if "n" can be decomposed into "count" number of perfect square numbers.
e.g. n=12, count=3:  true.
n=12, count=2:  false
"""
if cnt == 1:
return n in square_nums

for square_num in square_nums:
remainder = n - square_num
if is_divided_by(remainder, cnt-1):
return True
return False

for cnt in range(1, n+1):
if is_divided_by(n, cnt):
return cnt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

### # BFS

Use set instead of list for queue to eliminate the redundancy.

Complexity

time: $O(\frac{\sqrt{n}^{h+1} - 1}{\sqrt{n} - 1} ) = O(n^{\frac{h}{2}})$
space: $O\Big((\sqrt{n})^h\Big) = O(n^{\frac{h}{2}})$

def numSquares(self, n: int) -> int:
square_nums = [i**2 for i in range(1, int(sqrt(n))+1)]
level = 0
queue = {n}

while queue:
level += 1
next_queue = set()
for remainder in queue:
for square_num in square_nums:
if remainder == square_num:
return level # node found
elif remainder < square_num:
break
else:
queue = next_queue

return level

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

### # Math

In 1770, Lagrange's four-square theorem(or Bachet's conjecture) states that every natural number can be represented as the sum of four integer squares.

$p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2} \qquad \text{where } a_{0}, a_{1}, a_{2}, a_{3} \text{ are integers}$

In 1797, Gauss–Legendre three-square theorem states that $n$ is a sum of three squares precisely when $n$ is not of the form $4^{k}(8m+7)$ for any nonnegative integers $k$, $m$:

$n \ne 4^{k}(8m+7) \iff n = a_{0}^{2}+a_{1}^{2}+a_{2}^{2}$

So here is our strategy:

1. Check if n is of the form $4^{k}(8m+7)$. If yes, return $4$
2. Otherwise, check if n is a perfect square, or a sum of $2$ perfect squares
3. Else, n is a sum of $3$ perfect squares
def isSquare(self, n: int) -> bool:
sq = int(sqrt(n))
return sq*sq == n

def numSquares(self, n: int) -> int:
# four-square and three-square theorems
while (n & 3) == 0:
n >>= 2      # reducing the 4^k factor from number
if (n & 7) == 7: # mod 8
return 4

if self.isSquare(n):
return 1
# check if the number can be decomposed into sum of two squares
for i in range(1, int(n**(0.5)) + 1):
if self.isSquare(n - i*i):
return 2
# bottom case from the three-square theorem
return 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19