# 05. Get Minimum Squares
The problem can be found at the following link: ๐ [Question Link](https://www.geeksforgeeks.org/problems/get-minimum-squares0538/1)
## **๐งฉ Problem Description**
Given a positive integer `n`, find the minimum number of perfect squares (square of an integer) that sum up to `n`.
**Note:** Every positive integer can be expressed as a sum of square numbers since 1 is a perfect square, and any number can be represented as 1*1 + 1*1 + 1\*1 + ....
## **๐ Examples**
### Example 1
```cpp
Input: n = 100
Output: 1
Explanation: 10 * 10 = 100
```
### Example 2
```cpp
Input: n = 6
Output: 3
Explanation: 1 * 1 + 1 * 1 + 2 * 2 = 6
```
## **๐ Constraints**
* $1 \le n \le 10^4$
## **โ
My Approach**
The optimal approach uses **Lagrange's Four Square Theorem** combined with mathematical optimization to efficiently determine the minimum number of perfect squares needed:
### **Mathematical Optimization (Lagrange's Theorem)**
1. **Check for Perfect Square (Answer = 1):**
* Calculate the square root of n and verify if it's a perfect square.
* If yes, return 1 immediately.
2. **Check for Sum of Two Squares (Answer = 2):**
* Iterate through all perfect squares up to โn.
* For each square iยฒ, check if (n - iยฒ) is also a perfect square.
* If found, return 2.
3. **Check for Answer = 4 (Based on Lagrange's Theorem):**
* Remove all factors of 4 from n by repeatedly dividing.
* If the resulting number follows the form (8k + 7), return 4.
* This is based on the mathematical property that numbers of form 4^a(8b + 7) require exactly 4 squares.
4. **Default Answer = 3:**
* If none of the above conditions are met, return 3.
* By Lagrange's theorem, every positive integer can be expressed as sum of at most 4 perfect squares.
## **๐ Time and Auxiliary Space Complexity**
* **Expected Time Complexity:** O(โn), as we iterate up to the square root of n to check for sum of two squares, and perform constant time operations for other checks.
* **Expected Auxiliary Space Complexity:** O(1), as we only use a constant amount of additional space for variables regardless of input size.
## **๐งโ๐ป Code (C++)**
```cpp
class Solution {
public:
int minSquares(int n) {
if(int s = sqrt(n); s * s == n) return 1;
for(int i = 1; i * i <= n; i++)
if(int r = sqrt(n - i * i); r * r == n - i * i) return 2;
while(n % 4 == 0) n /= 4;
return n % 8 == 7 ? 4 : 3;
}
};
```
โก View Alternative Approaches with Code and Analysis
### ๐ **2๏ธโฃ Dynamic Programming Approach**
#### ๐ก Algorithm Steps:
1. Create a DP array where dp\[i] represents minimum squares for number i.
2. Initialize dp\[0] = 0 as base case.
3. For each number, try all perfect squares less than it.
4. Take minimum of all possible combinations to build the number.
```cpp
class Solution {
public:
int minSquares(int n) {
vector dp(n + 1, INT_MAX);
dp[0] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j * j <= i; j++)
dp[i] = min(dp[i], dp[i - j * j] + 1);
return dp[n];
}
};
```
#### ๐ **Complexity Analysis:**
* **Time:** โฑ๏ธ O(nโn) - Nested loops with square root boundary
* **Auxiliary Space:** ๐พ O(n) - DP array storage
#### โ
**Why This Approach?**
* Solves all subproblems systematically
* Can be extended to find actual square numbers
* Works for any positive integer
### ๐ **3๏ธโฃ BFS Level-Order Approach**
#### ๐ก Algorithm Steps:
1. Use BFS to explore all reachable numbers by subtracting perfect squares.
2. Each level represents using one more perfect square.
3. First time we reach 0 gives us the minimum count.
4. Track visited numbers to avoid redundant computations.
```cpp
class Solution {
public:
int minSquares(int n) {
queue q;
vector vis(n + 1);
q.push(n);
vis[n] = true;
int level = 0;
while(!q.empty()) {
int sz = q.size();
level++;
while(sz--) {
int cur = q.front();
q.pop();
for(int i = 1; i * i <= cur; i++) {
int next = cur - i * i;
if(next == 0) return level;
if(!vis[next]) {
vis[next] = true;
q.push(next);
}
}
}
}
return level;
}
};
```
#### ๐ **Complexity Analysis:**
* **Time:** โฑ๏ธ O(nโn) - BFS exploration with square root iterations
* **Auxiliary Space:** ๐พ O(n) - Queue and visited array
#### โ
**Why This Approach?**
* Guarantees shortest path to solution
* Intuitive level-based counting
* Natural fit for finding minimum operations
### ๐ **4๏ธโฃ Mathematical Optimization**
#### ๐ก Algorithm Steps:
1. Check if n is perfect square - return 1.
2. Remove all factors of 4 from n.
3. If remaining number โก 7 (mod 8), return 4.
4. Otherwise check for sum of two squares, else return 3.
```cpp
class Solution {
public:
int minSquares(int n) {
int s = sqrt(n);
if(s * s == n) return 1;
int temp = n;
while(temp % 4 == 0) temp /= 4;
if(temp % 8 == 7) return 4;
for(int i = 1; i * i <= n; i++)
if(s = sqrt(n - i * i); s * s == n - i * i) return 2;
return 3;
}
};
```
#### ๐ **Complexity Analysis:**
* **Time:** โฑ๏ธ O(โn) - Only checking up to square root
* **Auxiliary Space:** ๐พ O(1) - Constant space usage
#### โ
**Why This Approach?**
* Based on Lagrange's Four Square Theorem
* Eliminates impossible cases early
* Most efficient for single query
### ๐ **๐ Comparison of Approaches**
| ๐ **Approach** | โฑ๏ธ **Time Complexity** | ๐พ **Space Complexity** | โ
**Pros** | โ ๏ธ **Cons** |
| -------------------------- | ---------------------- | ----------------------- | -------------------------------- | -------------------------------- |
| ๐ฏ **Lagrange Theorem** | ๐ข O(โn) | ๐ข O(1) | โก Fastest single query | ๐งฎ Requires mathematical insight |
| ๐ **Dynamic Programming** | ๐ก O(nโn) | ๐ก O(n) | ๐ Reusable for multiple queries | ๐ Slower for large n |
| ๐ **BFS Level-Order** | ๐ก O(nโn) | ๐ก O(n) | ๐ฏ Intuitive minimum path | ๐พ High memory usage |
| ๐งฎ **Math Optimization** | ๐ข O(โn) | ๐ข O(1) | ๐ Optimal complexity | ๐ง Complex theorem application |
#### ๐ **Best Choice Recommendation**
| ๐ฏ **Scenario** | ๐๏ธ **Recommended Approach** | ๐ฅ **Performance Rating** |
| -------------------------------- | ---------------------------- | ------------------------- |
| ๐
**Single query optimization** | ๐ฅ **Lagrange Theorem** | โ
โ
โ
โ
โ
|
| ๐ **Multiple queries** | ๐ฅ **Dynamic Programming** | โ
โ
โ
โ
โ |
| ๐ **Learning/Interview** | ๐ฅ **BFS Approach** | โ
โ
โ
โ
โ |
| ๐ฏ **Competitive Programming** | ๐
**Math Optimization** | โ
โ
โ
โ
โ
|
## **โ Code (Java)**
```java
class Solution {
public int minSquares(int n) {
int s = (int)Math.sqrt(n);
if(s * s == n) return 1;
for(int i = 1; i * i <= n; i++) {
int r = (int)Math.sqrt(n - i * i);
if(r * r == n - i * i) return 2;
}
while(n % 4 == 0) n /= 4;
return n % 8 == 7 ? 4 : 3;
}
}
```
## **๐ Code (Python)**
```python
class Solution:
def minSquares(self, n):
s = int(n ** 0.5)
if s * s == n: return 1
for i in range(1, int(n ** 0.5) + 1):
r = int((n - i * i) ** 0.5)
if r * r == n - i * i: return 2
while n % 4 == 0: n //= 4
return 4 if n % 8 == 7 else 3
```
## ๐ง Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [๐ฌ Any Questions?](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let's make this learning journey more collaborative!
โญ **If you find this helpful, please give this repository a star!** โญ
***
#### ๐Visitor Count
