Given a natural number n, find the minimum number of perfect square numbers that sums up to n.

ex1: 12 = 4 + 4 + 4 ans: 3

ex2: 13 = 9 + 4 ans: 2

We call the result `minSq[n]`.

## Naive (BST):

For a number n, we need to divide the number into 2 parts, and recursively test whether if each part is a perfect square number. Since 1 is a perfect square number, essentially we need to test every possible combination of n. Take 6 for example:

``````6=0+6
6=1+5 -> 1=...  =>  1
->  5=0+5
5=1+4 -> 1=...=>  1
-> 4=0+4=> 1
4=1+3-> ... =>  5
4=2+2
5=2+3

6=2+4 -> 2=... =>  2
-> 4=0+4 =>  1
-> 4=1+3
-> 4=2+2
6=3+3
``````

`->` means next recurse, `=>` means the result of that branch. We see that some computation were done more than once. Such as finding minSq was done twice when splitting `6=1+1+4` and `6=2+4`.

## Observation:

We thus record the previous result. From the observation above, if we record `minSq` till `minSq[n-1]`, when splitting n, we don’t need to recurse, instead we look up from the `minSq` table, since a split of n is always less than n.

``````//112ms 46.53%
//15.2MB 18.13%
int numSquares(int n) {
vector<int> nsq = {0, 1, 2, 3};

for (int i = 4; i <= n; i++) {
nsq.push_back(i);
int j = 1;
int k = j * j;
while (k <= i) {
nsq[i] = min(nsq[i], 1+nsq[i-k]); //Keep the minimum number.
j++;
k = j*j;
}
}

return nsq[n];
}
``````

## Langrange Four Sqaure Theorem

A natural number can be written as sum of 4 perfect square numbers.

Thus for given n, the answer can only be 1, 2, 3, 4. (0 as addend not counted) Case 1: n is a perfect square number Case 2: the lesser root is less than sqrt(n), find it first than test the other half. Case 4: Case 3: Default

``````//Lagrange
//4ms 99.53%
//8.2MB 93.56%
bool isSquared(int n) {
int k = floor(sqrt(n));
return k * k == n;
}
int numSquares(int n) {
//1
int k = floor(sqrt(n));
if (k*k == n) return 1;

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

//4
//https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem
while (n % 4 == 0)
n = n / 4;
if ((n - 7) % 8 == 0)
return 4;

return 3;
}
``````