Perfect Squares

How it works

Lagrange's four square theorem states that every positive integer can be expressed as the sum of at most four perfect squares. Using additional number theory, we can determine the exact answer in constant time. If n is a perfect square, the answer is 1. If n can be written as the sum of two squares, the answer is 2. If n is of the form 4^k(8m+7), the answer is 4. Otherwise, the answer is 3.

Steps

1. Remove all factors of 4 from n (divide by 4 while divisible).
2. If the reduced n is congruent to 7 mod 8, return 4.
3. Check if the original n is a perfect square. If so, return 1.
4. Check if n can be expressed as the sum of two squares by testing all possible first squares. If so, return 2.
5. Otherwise, return 3.

Complexity

• Time complexity: O(sqrt {n})
• Space complexity: O(1)

Things to watch for

Not Recognizing Overlapping Subproblems

A common mistake is implementing plain recursion without memoization. The recursive solution recomputes the same subproblems many times (e.g., dfs(5) might be called from multiple paths). Without caching results, the solution becomes exponentially slow and will time out on larger inputs.

Incorrect Base Case or Initialization

Forgetting to handle the base case dp[0] = 0 or initializing the DP array incorrectly leads to wrong answers. The value dp[0] = 0 is crucial because it represents that zero squares are needed to sum to zero. Similarly, initializing other values to n (worst case of all 1s) ensures the minimum is correctly computed.

Iterating Over Non-Perfect-Squares

Some implementations mistakenly iterate through all numbers from 1 to target instead of only perfect squares. This wastes computation and can lead to incorrect state transitions. Always ensure the inner loop only considers values i where i * i <= target.

import math

class Solution:
    def numSquares(self, n: int) -> int:
        while n % 4 == 0:
            n //= 4

        if n % 8 == 7:
            return 4

        def isSquareNum(num):
            s = int(math.sqrt(num))
            return s * s == num

        if isSquareNum(n):
            return 1

        i = 1
        while i * i <= n:
            if isSquareNum(n - i * i):
                return 2
            i += 1

        return 3

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) {
            n /= 4;
        }

        if (n % 8 == 7) {
            return 4;
        }

        if (isSquareNum(n)) {
            return 1;
        }

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

        return 3;
    }

private:
    bool isSquareNum(int num) {
        int s = (int) sqrt(num);
        return s * s == num;
    }
};