## 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`) which sum to n.

Example 1:

``````Input:
n = 12
Output: 3

Explanation:
12 = 4 + 4 + 4.
``````

Example 2:

``````Input:
n = 13
Output: 2

Explanation:
13 = 4 + 9.
``````

Thoughts:

1. Dynamic Programming
1. sq[i] = ... to number i
2. sq[0] = 0
3. search from 1 to j (j ^2 <= i): sq[i] = min(sq[i], sq[i-j^2] + 1)
2. Static Dynamic Programming
1. sq[i]: ... to number i
2. sq[0] = 0
3. in the loop, each time push the result for sq[i] into ith of the container.
3. Mathematical Solution
1. Lagrange's Four Square Theorem: Any natural number can be represented by the sum of at most 4 perfect square numbers
2. number that need 4 perfect square meets: 4^k(8m + 7)
4. BFS
1. Each node a number
2. An edge between i and j exists if from node i to j, there is only one perfect number away.

Code 1:

``````class Solution {
public:
int numSquares(int n) {
vector<int> sq (n + 1, INT_MAX);
sq[0] = 0;
for(int i = 1; i < n + 1; i++){
for(int j = 1; j * j <= i ; j++){
sq[i] = min(sq[i], sq[i - j*j] + 1);
}
}

return sq[n];
}
};
``````

Code 2:

``````class Solution {
public:
int numSquares(int n) {
if( n <= 0 ) return 0;
static vector<int> sq ({0});
while(sq.size() <= n){
int m = sq.size();
int cur = INT_MAX;
for(int i = 1; i * i <= m; i++){
cur = min(cur, sq[m - i * i] + 1);
}

sq.push_back(cur);
}

return sq[n];
}
};
``````

Code 3: Lagrange's Four Square Theorem

``````class Solution {
private:
int is_square (int n){
int sqrt_n = (int) (sqrt(n));
return ( sqrt_n * sqrt_n == n);
}
public:
int numSquares(int n) {
// result of 1:
if(is_square(n)) return 1;

// Based on Lagrange's Four Square theorem, there
// are only 4 possible results: 1, 2, 3, 4.

// result of 4: 4^k(8m + 7)   https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem
while((n & 3) == 0) n >>= 2; // n%4 == 0
if((n & 7) == 7) return 4; // n%8 == 7

// result of 2:
int sqrt_n = (int)(sqrt(n));
for(int i = 1; i <= sqrt_n; i++){
if(is_square(n - i * i)) return 2;
}

return 3;
}
};
``````

Code 4: BFS: O(n*E)

``````class Solution {
public:
int numSquares(int n) {
if(n <= 0){
return 0;
}

vector<int> perfectSquares;
vector<int> record (n);

for(int i = 1; i * i <= n; i++){
perfectSquares.push_back(i * i);
record[i * i - 1] = 1;
}

if(perfectSquares.back() == n) return 1;

queue<int> q;
for(auto& num: perfectSquares){
q.push(num);
}

int count = 1;
while(!q.empty()){
count++;
int size = q.size();
for(int i = 0; i < size; i++){
int curNum = q.front();
for(auto& sqNum: perfectSquares){
if(curNum + sqNum == n) return count;
else if((curNum + sqNum < n) && (record[curNum + sqNum - 1] == 0)){
q.push(curNum + sqNum);
record[curNum + sqNum - 1] = 1; //add into the queue, mark as explored
}
else if( curNum + sqNum > n) break;
}
q.pop();
}
}

return 0;

}
};
``````

from zhukov's post