BiruLyu
7/6/2017 - 9:15 PM

## 279. Perfect Squares(1st).java

``````public class Solution {
public int numSquares(int n) {
// Based on Lagrange's Four Square theorem, there
// are only 4 possible results: 1, 2, 3, 4.
// // The result is 4 if and only if n can be written in the form of 4^k*(8*m + 7).
int t=n;
while ((t&3)==0) // n%4 == 0
t>>=2;
if ((t-7)%8==0)  // n%8 == 7
return 4;
int floor=(int)Math.floor(Math.sqrt(n));
// 开方结果为整数
if (floor==(int)Math.ceil(Math.sqrt(n)))
return 1;
while (floor>0)
{
t=n-floor*floor;
if ((int)Math.floor(Math.sqrt(t))==
(int)Math.ceil(Math.sqrt(t)))
return 2;
floor--;
}
return 3;
}
}``````
``````class Solution
{
private:
int is_square(int n)
{
int sqrt_n = (int)(sqrt(n));
return (sqrt_n*sqrt_n == n);
}

public:
// Based on Lagrange's Four Square theorem, there
// are only 4 possible results: 1, 2, 3, 4.
int numSquares(int n)
{
// If n is a perfect square, return 1.
if(is_square(n))
{
return 1;
}

// The result is 4 if and only if n can be written in the
// form of 4^k*(8*m + 7). Please refer to
// Legendre's three-square theorem.
while ((n & 3) == 0) // n%4 == 0
{
n >>= 2;
}
if ((n & 7) == 7) // n%8 == 7
{
return 4;
}

// Check whether 2 is the result.
int sqrt_n = (int)(sqrt(n));
for(int i = 1; i <= sqrt_n; i++)
{
if (is_square(n - i*i))
{
return 2;
}
}

return 3;
}
}; ``````
``````public class Solution {
public int numSquares(int n) {
if (n <= 0) return 0;
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];
}
}``````
``````class Solution
{
public:
int numSquares(int n)
{
if (n <= 0)
{
return 0;
}

// perfectSquares contain all perfect square numbers which
// are smaller than or equal to n.
vector<int> perfectSquares;
// cntPerfectSquares[i - 1] = the least number of perfect
// square numbers which sum to i.
vector<int> cntPerfectSquares(n);

// Get all the perfect square numbers which are smaller than
// or equal to n.
for (int i = 1; i*i <= n; i++)
{
perfectSquares.push_back(i*i);
cntPerfectSquares[i*i - 1] = 1;
}

// If n is a perfect square number, return 1 immediately.
if (perfectSquares.back() == n)
{
return 1;
}

// Consider a graph which consists of number 0, 1,...,n as
// its nodes. Node j is connected to node i via an edge if
// and only if either j = i + (a perfect square number) or
// i = j + (a perfect square number). Starting from node 0,
// do the breadth-first search. If we reach node n at step
// m, then the least number of perfect square numbers which
// sum to n is m. Here since we have already obtained the
// perfect square numbers, we have actually finished the
// search at step 1.
queue<int> searchQ;
for (auto& i : perfectSquares)
{
searchQ.push(i);
}

int currCntPerfectSquares = 1;
while (!searchQ.empty())
{
currCntPerfectSquares++;

int searchQSize = searchQ.size();
for (int i = 0; i < searchQSize; i++)
{
int tmp = searchQ.front();
// Check the neighbors of node tmp which are the sum
// of tmp and a perfect square number.
for (auto& j : perfectSquares)
{
if (tmp + j == n)
{
// We have reached node n.
return currCntPerfectSquares;
}
else if ((tmp + j < n) && (cntPerfectSquares[tmp + j - 1] == 0))
{
// If cntPerfectSquares[tmp + j - 1] > 0, this is not
// the first time that we visit this node and we should
// skip the node (tmp + j).
cntPerfectSquares[tmp + j - 1] = currCntPerfectSquares;
searchQ.push(tmp + j);
}
else if (tmp + j > n)
{
// We don't need to consider the nodes which are greater ]
// than n.
break;
}
}

searchQ.pop();
}
}

return 0;
}
};``````
``````//BFS in java
public class Solution {
//DP
public int numSquares2(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
int min = Integer.MAX_VALUE;
int j = 1;
while(i - j*j >= 0) {
min = Math.min(min, dp[i - j*j] + 1);
++j;
}
dp[i] = min;
}
return dp[n];
}

/*
Math
https://www.wikiwand.com/en/Lagrange%27s_four-square_theorem
https://www.wikiwand.com/en/Legendre%27s_three-square_theorem
A natural number is:
a sum of 3 squares if and only if it's not of the form 4a(8b+7) with integers a and b, either a, b can be 0.
a sum of 4 squares otherwise(of the form 4a(8b+7), neither a, b can be 0).
*/
private boolean is_square(int n) {
int sqrt_n = (int)(Math.sqrt(n));
return (sqrt_n*sqrt_n == n);
}
public int numSquares(int n) {
if(is_square(n)) return 1;  //check sum of 1 square
while (n % 4 == 0)
n /= 4;
if (n % 8 == 7)
return 4;   //check sum of 4 square
int sqrt_n = (int)Math.sqrt(n);
for(int i = 1; i<= sqrt_n; i++){
if (is_square(n-i*i)) return 2;  //check sum of 2 square
}
return 3;
}
}``````