# Perfect Squares
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/perfect-squares)
Canonical: https://scaleengineer.com/dsa/problems/perfect-squares
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [Citadel](https://scaleengineer.com/companies/citadel), [Revolut](https://scaleengineer.com/companies/revolut)
---
## Problem
Given an integer `n`, return _the least number of perfect square numbers that sum to_ `n`.

A **perfect square** is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, `1`, `4`, `9`, and `16` are perfect squares while `3` and `11` are not.

**Example 1:**

**Input:** n = 12
**Output:** 3
**Explanation:** 12 = 4 + 4 + 4.

**Example 2:**

**Input:** n = 13
**Output:** 2
**Explanation:** 13 = 4 + 9.

**Constraints:**

* `1 <= n <= 104`

# Approaches
## Recursive Approach
Use recursion to try all possible combinations of perfect squares that sum up to n.
**Time:** O(n^(h/2)) where h is the height of recursion tree · **Space:** O(sqrt(n)) for recursion stack
**Pros:** Simple to understand and implement; Works for small inputs
**Cons:** Exponential time complexity; Stack overflow for large inputs; Many redundant calculations
### Explanation
This approach uses recursion to find all possible combinations of perfect squares that sum up to n. For each number from 1 to sqrt(n), we try subtracting its square from n and recursively find the minimum number of perfect squares needed for the remaining number.

```java
class Solution {
    public int numSquares(int n) {
        if (n <= 0) return 0;
        return recursiveHelper(n);
    }
    
    private int recursiveHelper(int n) {
        if (n == 0) return 0;
        if (n < 0) return Integer.MAX_VALUE;
        
        int min = Integer.MAX_VALUE;
        for (int i = 1; i * i <= n; i++) {
            int result = recursiveHelper(n - i * i);
            if (result != Integer.MAX_VALUE) {
                min = Math.min(min, result + 1);
            }
        }
        return min;
    }
}
```
### Algorithm
1. Create a recursive helper function that takes the remaining number n
2. Base cases:
   - If n is 0, return 0
   - If n is negative, return MAX_VALUE
3. For each number i from 1 to sqrt(n):
   - Subtract i*i from n
   - Recursively find minimum squares for remaining number
   - Update minimum if a valid solution is found
4. Return minimum + 1

## Dynamic Programming
Use dynamic programming to store and reuse previously calculated results.
**Time:** O(n * sqrt(n)) · **Space:** O(n) for dp array
**Pros:** No redundant calculations; Works for all input sizes within constraints; Polynomial time complexity
**Cons:** Uses extra space; Still not the most efficient solution possible
### Explanation
This approach uses a dynamic programming array dp where dp[i] represents the least number of perfect squares that sum to i. For each number i, we try all possible perfect squares less than or equal to i and take the minimum.

```java
class Solution {
    public 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 j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}
```
### Algorithm
1. Create dp array of size n+1 initialized with MAX_VALUE
2. Set dp[0] = 0
3. For each number i from 1 to n:
   - For each perfect square j*j <= i:
     - dp[i] = min(dp[i], dp[i - j*j] + 1)
4. Return dp[n]

## Mathematical Approach (Lagrange's Four Square Theorem)
Use mathematical properties and Lagrange's Four Square theorem to find the answer.
**Time:** O(sqrt(n)) · **Space:** O(1)
**Pros:** Most efficient solution; Constant space complexity; Based on mathematical theorems; Works for all input sizes
**Cons:** Requires understanding of mathematical theorems; Less intuitive than other approaches
### Explanation
This approach uses Lagrange's Four Square theorem which states that every natural number can be represented as the sum of at most four perfect squares. Additionally, we can check if a number can be represented as sum of 1, 2, or 3 squares using mathematical properties.

```java
class Solution {
    public int numSquares(int n) {
        // Check if n is a perfect square
        if (isSquare(n)) return 1;
        
        // Check if n can be sum of two squares
        for (int i = 1; i * i <= n; i++) {
            if (isSquare(n - i * i)) return 2;
        }
        
        // Check if n = 4^k(8m + 7)
        while (n % 4 == 0) {
            n /= 4;
        }
        if (n % 8 == 7) return 4;
        
        return 3;
    }
    
    private boolean isSquare(int n) {
        int sqrt = (int) Math.sqrt(n);
        return sqrt * sqrt == n;
    }
}
```
### Algorithm
1. Check if n is a perfect square
2. Check if n can be represented as sum of two squares
3. Check if n is in form 4^k(8m + 7)
4. If none of above, return 3 (based on theorem)

# Solutions
### Java

```java
class Solution { public int numSquares ( int n ) { int m = ( int ) Math . sqrt ( n ); int [] f = new int [ n + 1 ]; Arrays . fill ( f , 1 << 30 ); f [ 0 ] = 0 ; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = i * i ; j <= n ; ++ j ) { f [ j ] = Math . min ( f [ j ], f [ j - i * i ] + 1 ); } } return f [ n ]; } }
```

### CPP

```cpp
class Solution { public: int numSquares ( int n ) { int m = sqrt ( n ); int f [ n + 1 ]; memset ( f , 0x3f , sizeof ( f )); f [ 0 ] = 0 ; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = i * i ; j <= n ; ++ j ) { f [ j ] = min ( f [ j ], f [ j - i * i ] + 1 ); } } return f [ n ]; } };
```

### Python

```python
class Solution : def numSquares ( self , n : int ) -> int : m = int ( sqrt ( n )) f = [ 0 ] + [ inf ] * n for i in range ( 1 , m + 1 ): for j in range ( i * i , n + 1 ): f [ j ] = min ( f [ j ], f [ j - i * i ] + 1 ) return f [ n ]
```