4
\$\begingroup\$

Leetcode problem 279 “Perfect Squares is:

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

I wrote the following solution:

def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        sqs = [0]
        nums = {}
        for x in range(1,n+1):
            nums[x] = 1
        for i in nums:
            if (i * i) in nums:
                sqs.append(i * i)              
        T = [x for x in range(n+1)]
        for i in range(1,len(sqs)):
            for j in range(1,n+1):
                if sqs[i] <= j:
                    T[j] = min(T[j],math.floor(j/sqs[i]) + T[j%sqs[i]])
        return T[n]

I wrote a dynamic-programming solution, storing results in a 1d array, but it seemed that due to the way I was originally calculating the perfect squares, the solution was timing out. I then modified the solution and came up with the one above, but the code is still causing a time out error when run against an input of 4635 for n.

How could this solution be optimized to avoid this timeout error?

\$\endgroup\$
7
\$\begingroup\$

Not an review, but an extended comment:

I don't know how this solution can be optimized. The expected solution is radically different, and is based on a couple of theorems from number theory.

You should check whether the number is

  • A perfect square (the answer is obviously 1), or
  • is a sum of 2 squares (the answer is obviously 2), or
  • not a Legendre's number, that is \$n = 4^a(8b + 7)\$ (the answer is 3)

Otherwise, the answer is 4.

\$\endgroup\$
  • \$\begingroup\$ should "is a Legendre's number" be "is not a Legendre's number"? \$\endgroup\$ – Jared Goguen Aug 17 '18 at 20:30
5
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Here is my solution. Thanks to @Martin R.

def numSquares(self, n):
    f = [float("inf")] * (n + 1)
    f[0] = 0
    sqs = [x*x for x in range(n + 1) if x*x <= n]
    for i in range(1, n + 1):
        for sq in sqs:
            if sq > i:
                break 
            f[i] = min(f[i], f[i - sq] + 1)
    return f[n]
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcom to Code Review, unlike stackoverflow.com we are here to provide pointers to the poster of the question suggesting how they can improve their code. Generally an alternate solution is not a good answer. Can you explain why the solution you provided is better and maybe provide some pointers to the poster on how they can improve their code. You might want to see codereview.stackexchange.com/help/how-to-answer. \$\endgroup\$ – pacmaninbw Apr 29 at 17:41
  • \$\begingroup\$ Got it. I'll take a look. Thanks for the user guide. \$\endgroup\$ – Charlie 木匠 Apr 30 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.