AlgoMaster Logo

Perfect Squares

Last Updated: March 28, 2026

medium
4 min read

Understanding the Problem

We need to express a given number n as a sum of perfect square numbers (1, 4, 9, 16, 25, ...) and find the minimum number of terms in that sum. We can reuse the same perfect square as many times as we want.

For example, 12 can be expressed in several ways: 1+1+1+1+1+1+1+1+1+1+1+1 (twelve 1s), or 4+4+4 (three 4s), or 9+1+1+1 (four terms). The best is 4+4+4 using only 3 squares.

If you think about it, this is fundamentally a "minimum coins" problem in disguise. The "coins" are perfect squares (1, 4, 9, 16, ...), the "amount" is n, and we want the fewest coins to make that amount. That connection to the Coin Change problem is the key observation that guides every approach below.

Key Constraints:

  • 1 <= n <= 10^4 --> With n up to 10,000, O(n sqrt(n)) is roughly 10,000 100 = 1,000,000 operations, which is very comfortable.
  • Every positive integer can be expressed as a sum of at most four perfect squares (Lagrange's Four-Square Theorem), so the answer is always 1, 2, 3, or 4.

Approach 1: Brute Force (Recursion)

Intuition

The most direct approach is recursion. For a given number n, we try subtracting every possible perfect square and recursively solve the smaller subproblem. If we subtract j*j from n, we need 1 + numSquares(n - j*j) squares. We try all valid perfect squares and take the minimum.

The base case is simple: numSquares(0) = 0 (zero needs zero squares). For any positive n, we iterate through 1, 4, 9, 16, ... up to n, and pick the choice that gives the smallest count.

Algorithm

  1. If n == 0, return 0.
  2. Initialize result to n (worst case: using all 1s gives exactly n terms).
  3. For each j from 1 while j * j <= n, recursively compute numSquares(n - j * j) and update result = min(result, 1 + numSquares(n - j * j)).
  4. Return result.

Example Walkthrough

1Start: numSquares(12). Try subtracting 1, 4, 9
n=12
12
8
4
0
1/4

Code

The recursion recomputes the same subproblems many times. What if we built solutions bottom-up, storing each result so we never recompute?

Approach 2: Dynamic Programming (Bottom-Up)

Intuition

Since the recursive solution has overlapping subproblems, we can use dynamic programming. We build a table dp where dp[i] is the minimum number of perfect squares that sum to i, filling it from dp[0] up to dp[n].

For each value i, we try every perfect square j*j that fits (where j*j <= i), and check: dp[i] = min(dp[i], dp[i - j*j] + 1). This is exactly the Coin Change DP, where the "coins" are perfect squares.

Algorithm

  1. Create an array dp of size n + 1, initialized to n + 1 (a safe upper bound).
  2. Set dp[0] = 0 (base case: zero needs zero squares).
  3. For each i from 1 to n, for each j from 1 while j * j <= i: dp[i] = min(dp[i], dp[i - j * j] + 1).
  4. Return dp[n].

Example Walkthrough

1Initialize dp[0]=0, rest=inf. Perfect squares up to 12: 1, 4, 9
0
0
1
13
2
13
3
13
4
13
5
13
6
13
7
13
8
13
9
13
10
13
11
13
12
13
1/10

Code

The DP solution builds the full table even when the answer is small. Can we model this as a shortest-path problem instead?

Approach 3: BFS (Shortest Path)

Intuition

Imagine a graph where each node is a number from 0 to n, and from any node i there is an edge to i - j*j for every perfect square j*j <= i. Finding the minimum number of perfect squares that sum to n is the same as finding the shortest path from n to 0. BFS naturally finds shortest paths in unweighted graphs.

This approach can terminate early. If the answer is 1 or 2, BFS finds it after exploring very few nodes.

Algorithm

  1. Create a queue and add n. Create a visited array to avoid reprocessing.
  2. Initialize depth = 0.
  3. While the queue is not empty, increment depth, process all nodes at the current level, and for each node subtract every possible j*j. If we reach 0, return depth. Otherwise enqueue unvisited results.

Example Walkthrough

1Start: queue=[12], depth=0
12
start
1/4

Code

Both DP and BFS are O(n * sqrt(n)). Can number theory give us a faster answer?

Approach 4: Math (Lagrange's Four-Square Theorem)

Intuition

Lagrange's Four-Square Theorem states that every positive integer is a sum of at most four perfect squares, so the answer is always 1, 2, 3, or 4. Legendre's Three-Square Theorem tells us exactly when the answer is 4: when n has the form 4^a * (8b + 7). With these two results, we check for 1 (is n a perfect square?), check for 4 (Legendre's form), check for 2 (enumerate pairs), and default to 3.

Algorithm

  1. Check if n is a perfect square. If yes, return 1.
  2. Check Legendre's condition: while n is divisible by 4, divide by 4. If the result mod 8 equals 7, return 4.
  3. For each j from 1 while j*j <= n, check if n - j*j is a perfect square. If any pair works, return 2.
  4. Otherwise, return 3.

Example Walkthrough

1Step 1: Is 12 a perfect square? sqrt(12)=3.46, no.
not square
12
3
11
8
3
1/4

Code