# Python Accepted Solution

• I've seen that the dp solution is not accepted in Python. Some use static dp in order to use it. And we can also solve it using number theory knowledge. But what if in a competition we don't know that theory? What if we are not allowed to use static dp? Here is an accepted solution using BFS:

``````class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""

q1 = [0]
q2 = []
level = 0
visited = [False] * (n+1)
while True:
level += 1
for v in q1:
i = 0
while True:
i += 1
t = v + i * i
if t == n: return level
if t > n: break
if visited[t]: continue
q2.append(t)
visited[t] = True
q1 = q2
q2 = []

return 0``````

• Very nice, finally someone did it :-)

You inspired me to write one as well, it's simpler but takes almost twice as much time as yours (688 ms yours, 1295 ms mine (average of three submissions)).

``````def numSquares(self, n):
sums = {0}
while n not in sums:
sums = {sum + i*i
for sum in sums
for i in xrange(1, int((n - sum)**0.5 + 1))}
return min(sums)
``````

• Hi, can you explain this algorithm? I have no idea..

• As I wrote, the algorithm is Breadth First Search (BFS). Imagine that you have a graph where vertices are numbers from 0 to n. 2 vertices are connected dirrectly if their values are different by a square number. for example: 1 and 2 connected, 2 and 3 connected, 2 and 6 connected, 2 and 11 connected, 1 and 5 connected, 1 and 10 connected, etc.

So starting from vertex 0, you look for the vertex n by BFS. The distance is exactly what we need to return.

• My code, improved the readability, runtime: 484 ms

``````class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
edges = [i*i for i in range(1, int(n**0.5)+1)]
visited = [False] * (n+1)
level = 0
children = [0]
while True:
level += 1
parents = children
children = []
for parent in parents:
for edge in edges:
child = parent + edge
if child == n:
return level
if child > n:
break
if visited[child]:
continue
visited[child] = True
children.append(child)
``````

And here is a improved version, saving the edge between the node and parent, only use edges which are equal or bigger than the saved edge when calculating children, runtime: 420 ms

``````class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
edges = [i*i for i in range(1, int(n**0.5)+1)]
edgesCount = len(edges)
visited = [False] * (n+1)
level = 0
children = {0:0}
while True:
level += 1
parents = children
children = {}
for parentV in parents:
startIndex = parents[parentV]
for edgeIndex in range(startIndex, edgesCount):
childV = parentV + edges[edgeIndex]
if childV == n:
return level
if childV > n:
break
if visited[childV]:
continue
visited[childV] = True
child = {childV:edgeIndex}
children.update(child)``````

• Inspired by u, I made some changes and the run time is improved to ~330 ms.

Consider it as a shortest path problem . See my explanation in the code.

The main performance improvement comes from using non-decreasing sequence of square numbers.
e.g., when checking 13, for the two possible sequences (4, 9) and (9, 4) only the former is checked.

``````class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
distance, q1, q2, label = 1, [(0, 1)], [], [10] * (n + 1)
'''
Shortest Path
Imagine a graph whose vertices are numbers from 0 to n. The lengths of all edges are 1.
Two vertices differ by any perfect square numbers are connected.
Starting from vertex 0, the shortest path to reach vertex n is the answer.
Since the length of all edges are the same, we can use a queue instead of heap to store
the vertices to be explored in each step.
Another improvement is that we only check non-decreasing sequence of square numbers, e.g.:
13 --> (4, 9), not (9, 4)
'''
while True:
for node, length in q1:
# non-decreasing sequence only
for edge in xrange(length, n+1):
next_node = node + edge*edge
if next_node == n:
return distance
elif next_node > n:
break
elif label[next_node] > distance:
label[next_node] = distance
# add node and the edge used last
q2.append((next_node, edge))
q1, q2 = q2, []
distance += 1
``````

• nice code.
is it slow because set runs slow than using the list `visited` ?

• I guess that plays a role, yes, but also the `xrange` and the `**0.5`. Don't know what has the biggest impact.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.