279. Perfect Squares

Problem¶

Given a positive integer n, return the minimum number of perfect squares whose sum is n.

n = 13 -> 2, because 13 = 9 + 4

Key trick¶

Treat each perfect square as a coin you can use repeatedly. If dp[i] is the fewest squares summing to i, then

\[ dp[0]=0,\qquad dp[i]=1+\min_{s^2\le i}dp[i-s^2]. \]

Trap¶

A greedy choice of the largest square can fail: \(12=9+1+1+1\), but \(12=4+4+4\). Compute states from smaller sums upward so every needed value is ready.

Why is it interesting?¶

This is the reusable unbounded coin change pattern. A faster solution exists using Legendre's and Lagrange's theorems, but DP transfers more readily to other interview problems.

Python solution¶

class Solution:
    def numSquares(self, n: int) -> int:
        squares = [x * x for x in range(1, n + 1) if x * x <= n]
        dp = [0] + [n + 1] * n

        for i in range(1, n + 1):
            for square in squares:
                if square > i:
                    break
                dp[i] = min(dp[i], dp[i - square] + 1)

        return dp[n]

Time complexity: \(O(n\sqrt n)\). Space complexity: \(O(n)\).

Comment on my solution¶

Your recurrence is correct and produces the minimum count.
Computing x**2 repeatedly can be replaced with a local square = x * x.
Its time complexity is \(O(n\sqrt n)\) and its space complexity is \(O(n)\), both acceptable for the given constraints.

class Solution:
    def numSquares(self, n: int) -> int:
        # 12 -> 3 (because 12 = 4 + 4 + 4)
        # 13 -> 2 (because 13 = 4 + 9)
        dp = [0] * (n + 1)
        dp[0] = 0

        for i in range(1, n+1):
            x = 1
            acc = float("inf")
            while x**2 <= i:
                acc = min(acc, dp[i - x**2] + 1)
                x += 1
            dp[i] = acc
        return dp[n]

Extra¶

Solution using Legendre and Lagrange theorems¶

import math


class Solution:
    def numSquares(self, n: int) -> int:
        def is_square(x: int) -> bool:
            root = math.isqrt(x)
            return root * root == x

        # One square.
        if is_square(n):
            return 1

        # Legendre's three-square theorem:
        # after removing factors of 4, values congruent to 7 mod 8
        # require exactly four squares.
        reduced = n
        while reduced % 4 == 0:
            reduced //= 4

        if reduced % 8 == 7:
            return 4

        # Two squares.
        for x in range(1, math.isqrt(n) + 1):
            if is_square(n - x * x):
                return 2

        # Lagrange guarantees at most four, and previous cases exclude
        # one, two, and four.
        return 3

Time complexity: \(O(\sqrt n)\).

Space complexity: \(O(1)\).

Lagrange's four-square theorem¶

For every integer \(n \ge 0\), there exist integers \(a,b,c,d\) such that \(n=a^2+b^2+c^2+d^2.\)

Legendre's three-square theorem¶

An integer \(n \ge 0\) can be written as \(n=a^2+b^2+c^2\) if and only if it is not of the form \(n=4^k(8m+7), \qquad k,m\in\mathbb{N}.\)

Therefore, after removing all factors of \(4\), a remainder congruent to \(7 \pmod 8\) requires exactly four squares.