5
\$\begingroup\$

I'm trying to solve this question:

Given a positive integral number n, return a strictly increasing sequence (list/array/string depending on the language) of numbers, so that the sum of the squares is equal to n².

If there are multiple solutions (and there will be), return the result with the largest possible values:

Basically, a squared number deconstructed into smaller squares. However, my code only works for smalls numbers efficiently (20 being roughly the max) and is exponentially slower onwards. How can I develop this code?

I tried optimising it by reducing the memory usage by setting comb to take out any bits of irrelevant data.

import itertools as it
from math import sqrt


def decompose(n):
    squares = [i ** 2 for i in range(1, n) if (i ** 2)/2 < n ** 2]
    comb = [list(i) for i in (reduce(lambda acc, x: acc + list(it.combinations(squares, x)),
                                     range(1, len(squares) + 1), [])) if sum(i) == n ** 2]
    print [int(sqrt(i)) for i in max(comb)]


decompose(20)

I am a beginner with Python so any optimisation tips will be greatly appreciated.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

I would suggest focusing on the nature of the answer. The requirement is to return the highest possible values, which also means the shortest sequence.

So I would suggest you start at n-1 and work your way down, checking increasingly long sequences until one sums to greater than n**2, in which case you can restart at n-2, etc.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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