Skip to interview prep
Apexed

386. What is the minimum number of perfect squares that sum to n?

MediumDynamic programming

Technical
Show model answer

DP: `best[0] = 0` and `best[x] = 1 + min(best[x − j²])` over j with j² ≤ x. There are n states and about √n choices each, so O(n√n) time and O(n) space. A BFS from n, subtracting squares level by level, finds the same answer and often stops early.

Number theory gives a much faster answer: by Lagrange's four-square theorem the result is at most 4. It is 4 exactly when n has the form 4^a(8b + 7) (Legendre's three-square theorem), 1 if n is a perfect square, 2 if n = i² + j² for some i (check in O(√n)), and 3 otherwise. Mentioning this after the DP shows depth.

What is the minimum number of perfect squares that sum to n — Data structures & algorithms interview question — Apexed