Room 04 · The Grind — 1-D Dynamic Programming

Perfect Squares

MEDIUM✓ CHIP-TIMEDLC #279 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Find the smallest count of square numbers (1, 4, 9, 16, …) that add up to a given n — same number can be reused as many times as needed.

A positive integer n arrives, and the job is to express it as a sum of perfect squares — 1, 4, 9, 16, and so on — using as few squares as possible, with any square reusable as many times as needed.

Only the count of squares used matters for the answer, not which squares were chosen or in what order they're listed. Every n has at least one valid decomposition, since 1 is itself a perfect square and can always be summed n times if nothing shorter works.

The output required is that smallest count of perfect squares summing exactly to n — a single integer, with no need to report which squares were actually used.

n is a positive integer
n stays within a range small enough for a square-root-time scan
the same square can be reused any number of times
an answer always exists since 1 is itself a perfect square

EX 01

n = 1

→ 1

minimum size, itself a square

EX 02

n = 3

→ 3

1 + 1 + 1, no better split exists

EX 03

n = 4

→ 1

a perfect square

The hintstake only what you need

HINT 1 THE NUDGE

Every amount i can be reached by landing a final square j² on top of some smaller amount i − j². What's the best way to combine the smaller amount's answer with that last jump?

HINT 2 THE STRUCTURE

dp[i] = 1 + the smallest dp[i − j²] over every square j² ≤ i, with dp[0] = 0. That's a clean bottom-up table, but it still costs a pass over every square for every amount.

HINT 3 ONE STEP FROM THE ANSWER

There's a number-theory shortcut: every n needs at most 4 squares (Lagrange). Check n itself for being a square (1), then check every j² for n − j² also being a square (2), then test Legendre's 4^a·(8b+7) form for the 4 case — anything left over is 3.

Coach's boardthe pattern, step by step

THE LAGRANGE CHECKPATTERN · LAGRANGE FOUR-SQUARE CHECKn = 11

VERDICT SO FAR

— empty —

STEP 1

n = 11. First check: is 11 itself a perfect square? 3² = 9 and 4² = 16 — neither hits 11, so no.

STEP 1 / 8 · ← → WORK TOO

The splitstwo paces, two languages

grind/perfect-squares.py — RACE PACE

LANG ▸

PACE ▸

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

        if is_square(n):
            return 1

        # Legendre's three-square theorem: n needs all 4 squares exactly when
        # n = 4^a * (8b + 7).
        m = n
        while m % 4 == 0:
            m //= 4
        if m % 8 == 7:
            return 4

        # otherwise n is either a sum of two squares, or of three
        i = 1
        while i * i <= n:
            if is_square(n - i * i):
                return 2
            i += 1
        return 3

TIME O(√N)SPACE O(1)PYTHON · RACE PACE · 24 LN

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            best = i  # worst case: i ones
            j = 1
            while j * j <= i:
                best = min(best, dp[i - j * j] + 1)
                j += 1
            dp[i] = best
        return dp[n]

TIME O(N·√N)SPACE O(N)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public int numSquares(int n) {
        if (isSquare(n)) {
            return 1;
        }

        int m = n;
        while (m % 4 == 0) {
            m /= 4;
        }
        if (m % 8 == 7) {
            return 4;
        }

        for (int i = 1; (long) i * i <= n; i++) {
            if (isSquare(n - i * i)) {
                return 2;
            }
        }
        return 3;
    }

    private boolean isSquare(int x) {
        int r = (int) Math.sqrt(x);
        for (int c = Math.max(0, r - 1); c <= r + 1; c++) {
            if ((long) c * c == x) {
                return true;
            }
        }
        return false;
    }
}

TIME O(√N)SPACE O(1)JAVA · RACE PACE · 32 LN

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int best = i;
            for (int j = 1; j * j <= i; j++) {
                best = Math.min(best, dp[i - j * j] + 1);
            }
            dp[i] = best;
        }
        return dp[n];
    }
}

TIME O(N·√N)SPACE O(N)JAVA · TRAINING PACE · 13 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED