279. Perfect Squares

  • 35.8%

https://leetcode.com/problems/perfect-squares/#/description

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

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.


https://discuss.leetcode.com/topic/24255/summary-of-4-different-solutions-bfs-dp-static-dp-and-mathematics

Summary of 4 different solutions (BFS, DP, static DP and mathematics)

Came up with the 2 solutions of breadth-first search and dynamic programming. Also “copied” StefanPochmann’s static dynamic programming solution (https://leetcode.com/discuss/56993/static-dp-c-12-ms-python-172-ms-ruby-384-ms) and davidtan1890’s mathematical solution (https://leetcode.com/discuss/57066/4ms-c-code-solve-it-mathematically) here with minor style changes and some comments. Thank Stefan and David for posting their nice solutions!

1.Dynamic Programming: 440ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution 
{
public:
int numSquares(int n)
{
if (n <= 0)
{
return 0;
}

// cntPerfectSquares[i] = the least number of perfect square numbers
// which sum to i. Note that cntPerfectSquares[0] is 0.
vector<int> cntPerfectSquares(n + 1, INT_MAX);
cntPerfectSquares[0] = 0;
for (int i = 1; i <= n; i++)
{
// For each i, it must be the sum of some number (i - j*j) and
// a perfect square number (j*j).
for (int j = 1; j*j <= i; j++)
{
cntPerfectSquares[i] =
min(cntPerfectSquares[i], cntPerfectSquares[i - j*j] + 1);
}
}

return cntPerfectSquares.back();
}
};

2.Static Dynamic Programming: 12ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution 
{
public:
int numSquares(int n)
{
if (n <= 0)
{
return 0;
}

// cntPerfectSquares[i] = the least number of perfect square numbers
// which sum to i. Since cntPerfectSquares is a static vector, if
// cntPerfectSquares.size() > n, we have already calculated the result
// during previous function calls and we can just return the result now.
static vector<int> cntPerfectSquares({0});

// While cntPerfectSquares.size() <= n, we need to incrementally
// calculate the next result until we get the result for n.
while (cntPerfectSquares.size() <= n)
{
int m = cntPerfectSquares.size();
int cntSquares = INT_MAX;
for (int i = 1; i*i <= m; i++)
{
cntSquares = min(cntSquares, cntPerfectSquares[m - i*i] + 1);
}

cntPerfectSquares.push_back(cntSquares);
}

return cntPerfectSquares[n];
}
};

3.Mathematical Solution: 4ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
}
};

4.Breadth-First Search: 80ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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;
}
};

https://discuss.leetcode.com/topic/23808/o-sqrt-n-in-ruby-c-c

O(sqrt(n)) in Ruby, C++, C

These solutions use some number theory (see explanation further down).

C++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int numSquares(int n) {
while (n % 4 == 0)
n /= 4;
if (n % 8 == 7)
return 4;
bool min2 = false;
for (int i=2; i<=n; ++i) {
if (i > n/i)
i = n;
int e = 0;
while (n % i == 0)
n /= i, ++e;
if (e % 2 && i % 4 == 3)
return 3;
min2 |= e % 2;
}
return 1 + min2;
}

C solution

Inspired by kevin36’s solution. We don’t really need to compute the prime factorization. Knowing that four squares always suffice and using the three-squares test is enough. Single-square and sum-of-two-squares cases can be done simpler.

1
2
3
4
5
6
7
8
9
10
11
12
int numSquares(int n) {
while (n % 4 == 0)
n /= 4;
if (n % 8 == 7)
return 4;
for (int a=0; a*a<=n; ++a) {
int b = sqrt(n - a*a);
if (a*a + b*b == n)
return 1 + !!a;
}
return 3;
}

Explanation

I happen to have given a little talk about just this topic a while back in a number theory seminar. This problem is completely solved, in the sense of being reduced to simple checks of a number’s prime factorization. A natural number is…

  • … a square if and only if each prime factor occurs to an even power in the number’s prime factorization.
  • … a sum of two squares if and only if each prime factor that’s 3 modulo 4 occurs to an even power in the number’s prime factorization.
  • … a sum of three squares if and only if it’s not of the form 4a(8b+7) with integers a and b.
  • … a sum of four squares. Period. No condition. You never need more than four.

Of course single squares can also be identified by comparing a given number with the square of the rounded root of the number.

The problem statement says “1, 4, 9, 16, …”, for some reason apparently excluding 0, but it really is a perfect square and the above theorems do consider it one. With that, you can for example always extend a sum of two squares a2+b2 to the sum of three squares a2+b2+02. Put differently, if n isn’t a sum of three squares, then it also isn’t a sum of two squares. So you can read the above statements as “… a sum of m (or fewer) squares”. Thanks to ruben3 for asking about this in the comments.

In my above solutions, I first divide the given number by 4 as often as possible and then do the three-squares check. Dividing by 4 doesn’t affect the other checks, and the n % 8 == 7 is cheaper than the prime factorization, so this saves time in cases where we do need four squares.

Armed with just the knowledge that you never need more than four squares, it’s also easy to write O(n) solutions, e.g.:

1
2
3
4
5
6
7
8
9
10
11
int numSquares(int n) {
int ub = sqrt(n);
for (int a=0; a<=ub; ++a) {
for (int b=a; b<=ub; ++b) {
int c = sqrt(n - a*a - b*b);
if (a*a + b*b + c*c == n)
return !!a + !!b + !!c;
}
}
return 4;
}

https://discuss.leetcode.com/topic/23812/static-dp-c-12-ms-python-172-ms-ruby-384-ms/2

Static DP, C++ 12 ms, Python 172 ms, Ruby 384 ms

There are so many “large” test cases that it’s worthwhile to keep data between test cases rather than recomputing from scratch all the time. At least in the slower languages. My dp tells the numbers of squares needed for the first integers, and when asked about a new n, I extend dp just as much as necessary.

C++ … 28 ms

1
2
3
4
5
6
7
8
9
10
int numSquares(int n) {
static vector<int> dp {0};
while (dp.size() <= n) {
int m = dp.size(), squares = INT_MAX;
for (int i=1; i*i<=m; ++i)
squares = min(squares, dp[m-i*i] + 1);
dp.push_back(squares);
}
return dp[n];
}

C++ … 12 ms

Switching the loops makes it less nice but faster:

1
2
3
4
5
6
7
8
9
10
int numSquares(int n) {
static vector<int> dp {0};
int m = dp.size();
dp.resize(max(m, n+1), INT_MAX);
for (int i=1, i2; (i2 = i*i)<=n; ++i)
for (int j=max(m, i2); j<=n; ++j)
if (dp[j] > dp[j-i2] + 1)
dp[j] = dp[j-i2] + 1;
return dp[n];
}

Python … 172 ms

1
2
3
4
5
6
7
class Solution(object):
_dp = [0]
def numSquares(self, n):
dp = self._dp
while len(dp) <= n:
dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
return dp[n]

There’s probably a cleaner way than using a global variable, but I’m new to Ruby and don’t know one.


https://discuss.leetcode.com/topic/26262/short-python-solution-using-bfs/2

Short Python solution using BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def numSquares(self, n):
if n < 2:
return n
lst = []
i = 1
while i * i <= n:
lst.append( i * i )
i += 1
cnt = 0
toCheck = {n}
while toCheck:
cnt += 1
temp = set()
for x in toCheck:
for y in lst:
if x == y:
return cnt
if x < y:
break
temp.add(x-y)
toCheck = temp

return cnt

The basic idea of this solution is a BSF search for shortest path, take 12 as an example, as shown below, the shortest path is 12-8-4-0:

image


https://discuss.leetcode.com/topic/23846/4ms-c-code-solve-it-mathematically

4ms C++ code - Solve it mathematically

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {  
public:
int is_square(int n){
int temp = (int) sqrt(n);
return temp * temp == n;
}
int numSquares(int n) {
while ((n & 3) == 0) //n%4 == 0
n >>= 2;
if ((n & 7) == 7) return 4; //n % 8 == 7
if(is_square(n)) return 1;
int sqrt_n = (int) sqrt(n);
for(int i = 1; i<= sqrt_n; i++){
if (is_square(n-i*i)) return 2;
}
return 3;
}
};

UPDATE: in order to understand, I suggest u read:

here is the Lagrange’s Four Square theorem - Limit the result to <= 4:

https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem

And this article, in which you can also find the way to present a number as a sum of four squares:

http://www.alpertron.com.ar/4SQUARES.HTM


https://discuss.leetcode.com/topic/23906/o-sqrt-n-about-0-034-ms-and-0-018-ms/2

O(sqrt(n)), about 0.034 ms (and 0.018 ms)

For better measurement, I wrapped the actual solution in a 10000-loop. This got accepted in 344 ms (every time in three submits), so without the wrapper it should take about 0.0344 ms. I tried a few variations and this is the fastest I managed to do.

(Update: After qgambit2’s challenge, I optimized my my original approach and now that’s my fastest, with about 180 ms.)

First I use the fact that four squares always suffice and the fact that four squares are only needed for numbers of the form 4a(8b+7). After that part, I know that the answer is 1, 2 or 3, and I try to build n as sum of one or two squares.

For that, I use a kind of two-pointers-approach. Instead of going through squares a2 and checking whether n-a2 is a square (which would involve computing lots of square roots), imagine you start with a=02 and b=floor(sqrt(n))2 and as long as a<=b, either make a the next larger square or make b the next smaller square, depending on whether the sum of the two squares is too small or too large (or return 2, if it’s exactly right).

But in order to improve speed further, I use that squares are sums of consecutive odd numbers starting at 1 (for example, 25=1+3+5+7+9), and my a and b aren’t squares but the corresponding odd numbers. And instead of computing the sum of the two squares, I just add to or subtract from n, trying to reach zero. This way, my main part doesn’t even have multiplications. Just simple addition/subtraction and comparisons.

The solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int numSquaresReal(int n) {
while (n % 4 == 0)
n /= 4;
if (n % 8 == 7)
return 4;
int a = -1, b = sqrt(n);
n -= b * b;
b += b + 1;
while (a <= b) {
if (n < 0)
n += b -= 2;
else if (n > 0)
n -= a += 2;
else
return a < 0 ? 1 : 2;
}
return 3;
}

The wrapper for better time measurement:

1
2
3
4
5
6
int numSquares(int n) {
int sum = 0;
for (int i=0; i<10000; i++)
sum += numSquaresReal(n);
return sum / 10000;
}

488ms, 26.95%, June.15th, 2016

https://leetcode.com/discuss/62229/short-python-solution-using-bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n < 2:
return n
lst = []
i = 1
while i * i <= n:
lst.append( i * i )
i += 1
cnt = 0
toCheck = {n}
while toCheck:
cnt += 1
temp = set()
for x in toCheck:
for y in lst:
if x == y:
return cnt
if x < y:
break
temp.add(x-y)
toCheck = temp

return cnt

Solution 2:

208ms, 60.99%, June.15th, 2016

https://leetcode.com/discuss/56993/static-dp-c-12-ms-python-172-ms-ruby-384-ms

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
_dp = [0]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
dp = self._dp
while len(dp) <= n:
dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
return dp[n]
谢谢你,可爱的朋友。