Return the minimum number of perfect squares (1, 4, 9, 16, …) that sum to exactly n.
summingSquares(n)
Assume n >= 0 (and summingSquares(0) = 0).
summingSquares(12) // → 3 (4 + 4 + 4)
summingSquares(9) // → 1 (9)
summingSquares(6) // → 3 (4 + 1 + 1)
Structurally identical to coin change, except the "coins" are perfect squares (1, 4, 9, 16, ...) up to the target, determined by the amount itself rather than given directly. The last square used is some s*s not exceeding the amount; the minimum count is 1 plus the smallest "minimum squares for amount - s*s" over every valid s.
An amount of 0 needs zero squares.
Different combinations of squares chosen in different orders land on the same remaining amount — using 4 then 1, or 1 then 4, leave the same remainder. The naive recursion re-solves that same remainder every time it's reached, even though the answer never changes. This compounds exponentially as the target grows.
The minimum squares needed depends only on the remaining amount, never on which squares got you there. Cache from remaining amount to minimum count. Check before recursing; otherwise try every square up to the amount, recurse on the remainder, take the minimum of 1 + result, cache, return.
Only n+1 distinct remaining amounts arise, each solved once, trying roughly √amount candidate squares — about O(n·√n) instead of exponential. Same pattern as coin-change minimization: the state is fully captured by the remaining target.
def summing_squares(n):
memo = {}
def best(amount):
if amount == 0:
return 0
if amount in memo:
return memo[amount]
m = float("inf")
s = 1
while s * s <= amount:
c = 1 + best(amount - s * s)
if c < m:
m = c
s += 1
memo[amount] = m
return m
return best(n)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.