Minimum perfect squares needed to sum up to a target

Question

I'm trying to solve this problem

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

I've come up with a solution that works correctly but times out on large inputs:

from collections import defaultdict
class Solution:
    def numSquares(self, n: int) -> int:
        coins = []
        for i in range(1, n+1):
            if i**2>n:
                break 
            coins.append(i**2)
        min_coins_to_make = defaultdict(lambda :float("inf"))
        min_coins_to_make[0] = 0 
        for coin in coins:
            if coin > n:
                break 
            for target in range(coin, n+1):
                min_coins_to_make[target] = min(min_coins_to_make[target], 1+min_coins_to_make[target-coin])
        if min_coins_to_make[target] == float("inf"):
            return 0 
        return min_coins_to_make[target]

How do I optimize it in terms of time and space complexity?

https://leetcode.com/problems/perfect-squares/

Answer 1

I won't specifically address the execution time concerns to begin with; there are other issues:

Don't use a class

There's no reason for this to be a class. You have one method and you don't even reference self. In theory you could remove self and mark it a @staticmethod, but really it should just be a function without a class.

Reuse variables

Make this variable -

i2 = i**2

since it's used twice. The same goes for min_coins_to_make[target].

Loop limit

    for coin in coins:
        if coin > n:
            break 

That termination condition will be true if coin > n, but coin == i**2. i**2 > n will never be true, because in the previous loop,

        if i**2>n:
            break 

So can't you just write for coin in coins without an interior termination condition?

Answer 2

Here

if min_coins_to_make[target] == float("inf"):
    return 0 
return min_coins_to_make[target]

you use the fact that target has the last value from a preceding (nested) loop, and that happens to be n. It would be more clear to use n directly instead:

if min_coins_to_make[n] == float("inf"):
    return 0 
return min_coins_to_make[n]

Then note that the if-condition can never be true, so that you can remove that test: Every positive integer \$ n \$ can be written as $$ n = \underbrace{1 + 1 + \ldots + 1}_{n \text{ terms}} $$ which makes it a sum of \$ n \$ perfect squares. (Actually every positive integer can be written as the sum of at most four squares according to Lagrange's four-square theorem.)

This

coins = []
for i in range(1, n+1):
    if i**2>n:
        break 
    coins.append(i**2)

can be written as a list comprehension:

coins = [i * i for i in range(1, int(math.sqrt(n)) + 1)]

Answer 3

You can remove the coins variable altogether and replace it with a generator of squares:

for coin in (x**2 for x in itertools.count(1)):
    ...

You don't necessarily need a defaultdict with a lambda, since you are going to create the all the values in the dict anyway (defaultdict is more appropriate if you don't know in advance what keys you'll need):

min_coins_to_make = {i: i for i in range(n)}

(which takes care of the square of 1, too, so you can start your count at 2, realistically)

In terms of space and complexity, space is O(N), complexity is O(N*Log(N)) (it's actually a Harmonic number (sum(1/i for i < n)), but it converges to ln(N)). I don't see a better option right now.

One other way to look at the problem could be to go backward from large squares, that way you can stop when the square you're looking at is smaller that N/current best (as you'd have to replace a bigger element, hence increasing the total count.) or when you somehow know that the current solution is optimal. I don't know exactly how you'd go about this approach, though.

Answer 4

If you want to optimize your code, optimize the algorithm first.

Thanks to Lagrange's four-square theorem, you know you will need at most four squares of positive integers.

• You can pretend that the last number chosen will succeed.
• You can impose that the next number chosen is not greater.
• You can pretend that the next try will be no worse than the best to date.
• If you get a solution fast, you can cull the search-space, so start at the big end.

Every selection will be similar, though under potentially more severe constraints, so use recursion:

def numSquaresImpl(n: int, upper: int, num: int) -> int:
    upper = min(int(sqrt(n)) + 1, upper)
    while upper ** 2 > n:
        upper = upper - 1
    if upper ** 2 == n:
        return 1
    if num <= 2:
        return 2
    lower = max(0, int(sqrt(n // num)) - 1)
    while upper >= lower:
        r = numSquaresImpl(n - upper ** 2, upper, num - 1) + 1
        upper = upper - 1
        if r < num:
            if r == 2:
                return 2
            num = r
            lower = max(0, int(sqrt(n // num)) - 1)
    return num
def numSquares(n: int) -> int:
    return numSquaresImpl(n, n, 4) if n > 0 else 0

_{Warning: I only proved this correct, I didn't run it. Also, I rarely do Python.}

As others already said, wrapping a pure function in a class without any good reason makes no sense.

Answer 5

Lagrange's_four-square_theorem says:

every natural number can be represented as the sum of four integer squares.

The theorem allows the squares to be zero, so in context of our problem we will say that every natural number can be represented as the sum of four or less integer squares. It means that when we want to determine which square is the largest in the "shortest" sum, it must be greater than n // 4. It is the most significant optimization of the code below, it is implemented in the line elif square > n_4:. The code runs in 1136 ms and 30.7 MB on leetcode. I believe it can be better improved and explained but the theorem is the main idea.

import collections


Parameters = collections.namedtuple('Parameters', ['n', 'last_index', 'num_squares'])


class Solution:
    def numSquares(self, n):
        squares = [i ** 2 for i in range(1, int(n ** 0.5) + 1)]
        min_num = n
        lst = [Parameters(n, len(squares) - 1, 0)]
        while lst:
            new_lst = []
            for parameters in lst:
                if parameters.num_squares < min_num:
                    n_4 = parameters.n // 4
                    for index in range(parameters.last_index + 1):
                        square = squares[index]
                        if square == parameters.n:
                            min_num = min(min_num, parameters.num_squares + 1)
                        elif square > parameters.n:
                            break
                        elif square > n_4:
                            new_lst.append(
                                Parameters(
                                    parameters.n - square,
                                    index,
                                    parameters.num_squares + 1
                                )
                            )
            lst = new_lst
        return min_num