Caching
You are using sums
as a cache for your dynamic programming. Python comes with built-in caching (functools.lru_cache
), so you don't need to implement your own. Using it will avoid polluting the global namespace.
Integer Square-Root
With Python3.8 comes a built-in math.isqrt
, rendering the idiom int(n**(1/2))
obsolete.
Unnecessary filtering
squares = [i**2 for i in range(1, isqrt(n) + 1)]
while len(squares) and squares[-1] > n:
squares.pop()
Here, you are generating all the squares up to (and including if it is a perfect square) n
. Then, you check if the last item is larger than n
. It is impossible for it to be, so squares.pop()
will never be executed, making the entire while
loop redundant code which can be deleted.
Unnecessary (and suspicious) minimum
s = 2**31
for i in squares:
s = min(s, numSquares(n - i) + 1)
Here, 2**31
is used as a value larger than any possible value, so you can compute the minimum in the for
loop. But is it really larger than any possible value??? I can think of larger values, but perhaps it comes from the challenge text.
Still, Python provides a better way: the min(...)
function and list comprehension:
s = min(numSquares(n - i) + 1 for i in squares)
This loops through all squares, and evaluates numSquares(n - i) + 1
for each one, and selects the minimum value. No magic "value larger than any possible value" value is required.
Still, it can be made even more efficient. If there are 10,000 squares, we add one to each result, and take the minimum. That's 10,000 plus one operations. If we compute the minimum value, and add one to that, we've saved 9,999 additions.
s = min(numSquares(n - i) for i in squares) + 1
Unnecessary list creation
The code would now read:
squares = [i**2 for i in range(1, isqrt(n) + 1)]
s = min(numSquares(n - i) for i in squares) + 1
We create a list of squares
and then immediately loop through that list exactly once, and never use it again. Creating the list is an unnecessary step, that consumes memory and wastes time. Just compute the squares on the fly!
s = min(numSquares(n - i ** 2) for i in range(1, isqrt(n) + 1)) + 1
PEP-8
Functions and variables should be in snake_case
, not mixedCase
. Your function should be named num_squares
.
There should be a space around binary operators like **
and /
.
Variable names like s
are meaningless. Variable names should be descriptive. s
is the minimum count of the terms summing to n
; min_terms
would be more descriptive.
Updated Code
from functools import lru_cache
from math import isqrt
@lru_cache(maxsize=None)
def num_squares(n: int) -> int:
root_n = isqrt(n)
if root_n ** 2 == n:
return 1
return min(num_squares(n - i ** 2) for i in range(1, root_n + 1)) + 1
Further improvements
Consider 10001. It is not a perfect square. So you start subtracting squares off it, beginning with \$1^2\$ and discover \$10001 - 1^2 = 100^2\$, for min_terms
of 2. You should stop searching; there will be no better answer. But instead, you will continue with \$10001 - 2^2\$, and figure out the num_squares()
of that, and then try
\$10001 - 3^2\$ and so on. This is all busy work.
Determining how to prune the search tree left as exercise to student.