AlgoMaster Logo

Perfect Squares

mediumFrequency7 min readUpdated June 23, 2026

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.

This is a "minimum coins" problem. 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 guides every approach below.

Key Constraints:

  • 1 <= n <= 10^4. With n up to 10,000, an O(n sqrt(n)) solution runs in about 10,000 100 = 1,000,000 operations, well within limits.
  • Every positive integer is 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

For a given number n, 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. Try all valid perfect squares and take the minimum.

The base case is 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. The next approach builds solutions bottom-up and stores each result so nothing is recomputed.

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 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 always builds the full table, even when the answer is 1 or 2. Modeling the problem as a shortest path lets the search stop as soon as it reaches 0.

Approach 3: BFS (Shortest Path)

Intuition

Build 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. Every edge represents using one perfect square, so the minimum number of squares summing to n equals the length of the shortest path from n to 0. Since all edges have equal weight, BFS finds that shortest path.

Because BFS explores level by level, it stops the moment it reaches 0. If the answer is 1 or 2, it finishes after exploring 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)). Two results from number theory reduce the answer to a handful of constant-time checks.

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 identifies exactly when four are required: when n has the form 4^a * (8b + 7). These two results turn the problem into a short sequence of checks. Test for 1 (is n a perfect square?), then for 4 (Legendre's form), then for 2 (does some n - j*j equal a square?). If none of those hold, the answer must be 3, since Lagrange caps it at 4 and Legendre has already ruled 4 out.

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