Review of your existing code
(with some small performance improvements):
nums = {}
for x in range(1,n+1):
nums[x] = 1
creates a dictionary with keys from 1 to n+1, all having the value
1. A more Pythonic way to achieve the same is with dictionary
comprehension:
nums = { x: 1 for x in range(1, n+1) }
This dictionary is then used to create a list of all square numbers
not exceeding n:
sqs = [0]
for i in nums:
if (i * i) in nums:
sqs.append(i * i)
But the same can be done without the help of a dictionary:
sqs = [i * i for i in range(1, n + 1) if i * i <= n ]
or even more efficiently:
sqs = [i * i for i in range(1, math.floor(math.sqrt(n)) + 1)]
Note also that the parentheses in above if-condtion are not needed.
Instead of iterating of the indices of the sqs list
for i in range(1,len(sqs)):
# do something with `sqs[i]` ...
it is better to iterate over the list directly:
for s in sqs:
# do something with `s` ...
math.floor(j/sqs[i]) can be done with an integer division j // sqs[i].
If the order of the nested loops is interchanged then one can leave
the inner loop early if the square number becomes too large:
for j in range(1, n + 1):
for s in sqs:
if s <= j:
T[j] = min(T[j], j // s + T[j % s])
else:
break
It is sufficient to update
T[j] = min(T[j], 1 + T[j - s])
because T[j - s] is already the correct optimal value.
With these changes, the function already becomes a bit faster.
My simple performance benchmark is
N = 500
start = time.time()
l = [numSquares(x) for x in range(1, N)]
end = time.time()
print((end - start) * 1000)
On a 1.2 GHz MacBook I measured roughly 1000 milliseconds with your
original code and 600 milliseconds with the improved version
def numSquares(n):
sqs = [i * i for i in range(1, math.floor(math.sqrt(n)) + 1)]
T = [x for x in range(n+1)]
for j in range(1, n + 1):
for s in sqs:
if s <= j:
T[j] = min(T[j], 1 + T[j - s])
else:
break
return T[n]
Further possible performance improvements are:
- Check some simple cases (e.g
n <= 3) in advance.
- Check in advance if
n is a perfect square.
Unfortunately, all these changes are not good enough to pass the
LeetCode challenge.
Some more remarks:
- The PEP8 online check reports many PEP8 coding style violations,
mainly missing (horizontal) whitespace.
- Some variable names can be improved, e.g.
squares instead of
sqs. It is also unclear what T stands for.
An alternative approach
As it turns out, it is more efficient to compute sets with sums of 2, 3, 4, ...
square numbers, until the given number occurs in such a set.
This leads to the following implementation
def numSquares(n):
if n <= 3:
return n
squares = { i * i for i in range(1, math.floor(math.sqrt(n)) + 1) }
sums = squares
for i in range(1, n):
if n in sums:
return i
sums = { a + b for a in squares for b in sums if a + b <= n }
The above benchmark runs in approximately 100 milliseconds (i.e.
faster than the original by a factor of 10), and this
also passed the LeetCode challenge.
