The O(n) Club: Perfect Squares Problem—Counting Squares Without Losing Yours

The O(n) Club: Perfect Squares Problem—Counting Squares Without Losing Yours

⚡ TL;DR

Given a number n, find the minimum count of perfect squares (like 1, 4, 9, 16, …) that sum up to n.
Brute-force? Sure—if you like stack overflows and watching your runtime crumble. But with dynamic programming, you’ll get it done before your coffee cools:

// Dynamic Programming – shockingly not awful
int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int sq = 1; sq * sq <= i; sq++) {
            dp[i] = Math.min(dp[i], dp[i - sq * sq] + 1);
        }
    }
    return dp[n];
}

🧠 How Devs Usually Mess This Up

• Missing the point about the count. The problem wants only the smallest number of squares, not the shopping list. So stop worrying about the actual numbers—you’re not delivering a pizza order.
• Looping every number to n. Nope. Only perfect squares less than or equal to n are invited. Sorry, 8. You’re not on the list.
• Recursion fan club, assemble! It might work for n=5, but past n=100? Suddenly you’re writing a stress test for your laptop fan.

🔍 What’s Actually Going On

Imagine you’re moving along a game board and can only jump ahead by 1, 4, 9, 16 spaces at a time—that’s how perfect squares work here. The question? What’s the minimum number of jumps to land exactly on space n. Not how you get there—just how few hops you need. It’s basically Coin Change with coins nobody sane would want.

Dynamic Programming keeps a table of the best ways to reach each number—like leaving yourself sticky notes as you go. BFS works too, treating each square subtract as a “move” and finding the shortest hop chain to zero.

🛠️ PseudoCode

• Step 1: List all perfect squares ≤ n.
  

  for (int sq = 1; sq * sq <= n; sq++) squares.add(sq * sq);

  Yes, only the square numbers.
• Step 2: Set up a dp array of n+1, start with dp[0]=0 (using zero squares for zero).
  

  int[] dp = new int[n + 1];
  Arrays.fill(dp, Integer.MAX_VALUE);
  dp[0] = 0;

• Step 3: For each number from 1 to n:
  • For every perfect square ≤ i, set dp[i] = min(dp[i], dp[i - square] + 1)

for (int i = 1; i <= n; i++) {
    for (int sq : squares) {
        if (sq > i) break;
        dp[i] = Math.min(dp[i], dp[i - sq] + 1);
    }
}