Problem

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

Example 1:

Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

Thought Process

• since 1 is a perfect square, so for any n, there must be a solution, the worst case is n
• I tried the brute force solution but failed, i.e. find the biggest perfect score the number can hold e.g. 9 for 12:
• e.g. 12 = 9 + 3, and 3 can only be 1 + 1 + 1, giving an result of 4
• however, 12 = 4 + 4 + 4, which is 3
• One solution is to model the problem as an unweighted graph:
• for numbers from 0 to n, each number is a point
• connect two points x, y if the distance (y-x) is a perfect square number, connect these two points
• Then the problem is essentially a finding the shortest path problem, which can be solved with Broad First Search

Code

from collections import deque

class Solution:

def numSquares(self, n):
# create a queue
q = deque()
# store the point and number of steps to get to this point
# initially, store n, and 0 steps to get to n first
pair = (n, 0)

# append pair to queue
q.append(pair)

# loop as long as q is not empty
while q:
# check the current pair at the head of queue
curr = q.popleft()
num = curr
step = curr

if num == 0:
# for 0 return 0
return step

i = 1
for i in range(num - i**2 + 1):
# as long as num can hold another perfect square
pair = (num - i**2, step + 1)
q.append(pair)

This solution is correct logically however, it will have TLE issue. Because there were too many repetitive calculations.

Complexity

• Time complexity is O(n**2), a nested while and for loop is used
• Space complexity is O(n), a deque is used to store node and its level info

Optimization

Due to TLE, one way to optimize the solution is to record whether a num is visited, if it's already visited, no need to push it into the q to avoid repetition and waste on resources.

from collections import deque

class Solution:
def numSquares(self, n: int) -> int:
# create a queue
q = deque()
# store the point and number of steps to get to this point
# initially, store n, and 0 steps to get to n first
pair = (n, 0)

# append pair to queue
q.append(pair)

# create a visited list, initialized with all False
visited = [False] * (n+1)
# since (n,0) is append in queue already, so n is already visited
visited[n] = True

# loop as long as q is not empty
while q:
# check the current pair at the head of queue
curr = q.popleft()
num = curr
step = curr

if num == 0:
# for 0 return 0
return step

i = 1

while True:
a = num - i**2
# as long as num can take another perfect square
# a is the next perfect square
if a < 0:
break
if not visited[a]:
pair = (a, step + 1)
q.append(pair)
visited[a] = True

i += 1

def test():
sol = Solution()
print(sol.numSquares(12))
print(sol.numSquares(13))
print(sol.numSquares(1))

test()

3 2 1

White Board

Below is the white board: