Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Perfect Squares
• Topics: Math, Dynamic Programming, Breadth-First Search

Problem gist

Given a positive integer n, the task is to return the fewest perfect square numbers whose sum is exactly n. A perfect square is a number such as 1, 4, 9, 16, and so on.

For example, 12 can be written as 4 + 4 + 4, so the answer is 3. The goal is not to list the squares, only to return the minimum count.

The dynamic programming way to think about the problem is simple: every answer for n can be built by picking one square s * s and then solving the smaller problem n - s * s. That gives a practical O(n * sqrt(n)) solution. The sharper solution uses number theory to reduce the answer to a few checks.

Deriving the optimal solution

Lagrange’s four-square theorem says every positive integer can be written as the sum of at most four perfect squares. That means the answer is always one of 1, 2, 3, or 4.

Now the problem becomes classification:

• If n is already a perfect square, the answer is 1.
• If n can be written as a^2 + b^2, the answer is 2.
• Legendre’s three-square theorem tells us exactly when a number cannot be represented by three squares: after removing all factors of 4, if the remaining number is congruent to 7 modulo 8, the answer must be 4.
• If none of the above cases apply, the answer is 3.

The important interview insight is that the theorem does not replace reasoning; it narrows the search space. Once every number is known to need at most four squares, each case can be tested directly.

Python solution

from math import isqrt


class Solution:
    def numSquares(self, n: int) -> int:
        """Return the minimum number of perfect squares that sum to n."""
        if n <= 0:
            return 0

        if self._is_square(n):
            return 1

        reduced = self._remove_factors_of_four(n)
        if reduced % 8 == 7:
            return 4

        if self._can_be_two_squares(n):
            return 2

        return 3

    @staticmethod
    def _is_square(value: int) -> bool:
        root = isqrt(value)
        return root * root == value

    @staticmethod
    def _remove_factors_of_four(value: int) -> int:
        while value % 4 == 0:
            value //= 4
        return value

    def _can_be_two_squares(self, value: int) -> bool:
        limit = isqrt(value)
        for first_root in range(1, limit + 1):
            first_square = first_root * first_root
            if self._is_square(value - first_square):
                return True
        return False

This runs in O(sqrt(n)) time because the only loop checks whether n is a sum of two squares. It uses O(1) extra space.

Interview follow-ups

What if the interviewer asks for one actual decomposition, not just the count?

The theorem-based solution is excellent for the count, but it does not naturally return the square values. For reconstruction, use dynamic programming with parent pointers.

Let dp[x] store the fewest squares needed to sum to x, and let previous_square[x] store the square chosen when the best answer for x was last improved. For every x from 1 to n, try each square s * s <= x, and update dp[x] from dp[x - s * s] + 1. After the table is filled, start at n, repeatedly subtract previous_square[current], and collect those squares.

This works because each state is built from strictly smaller states that have already been solved. The tradeoff is higher cost: O(n * sqrt(n)) time and O(n) space, but it gives a concrete decomposition.

What if many queries arrive for different values of n?

If the queries are known in advance, find the maximum requested value and build one DP table up to that maximum. Then each query can be answered in O(1) time by reading dp[n].

This is useful when the constraints favor repeated lookups over one isolated call. The preprocessing costs O(max_n * sqrt(max_n)) time and O(max_n) space, but it avoids recomputing the same subproblems for every query.

If only the count is required and each query is independent, the theorem-based method is often still attractive because each query is only O(sqrt(n)) with constant space.

What if number theory is not allowed?

Use breadth-first search from n toward 0. Each BFS edge subtracts one perfect square, so reaching 0 at level k means n can be represented using k squares. Because BFS explores by increasing number of moves, the first time it reaches 0 is the optimal answer.

The BFS view is often easier to explain than the theorem view: each level represents using one more square. Its worst-case complexity is similar to DP, roughly O(n * sqrt(n)), with O(n) space for visited remainders. It can be faster in practice for some inputs because it stops as soon as 0 is reached.

What if n is extremely large?

For very large n, the DP and BFS approaches become too memory-heavy. The theorem-based solution is the right direction because it keeps space constant and only loops up to sqrt(n).

The remaining bottleneck is the two-square check. If sqrt(n) itself is too large, the interviewer may be steering toward deeper number theory: a number can be expressed as a sum of two squares exactly when every prime factor congruent to 3 modulo 4 appears with an even exponent. That can reduce the two-square decision to prime factorization. The tradeoff is that factorization may be expensive for arbitrary huge numbers, so the best method depends on the numeric range and whether a factorization library or precomputed primes are available.