Problem statement
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Example 1
Input: n = 9
Output: 1
Explanation: 9 is already a perfect square.
Example 2
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
Example 3
Input: n = 7
Output: 4
Explanation: 7 = 4 + 1 + 1 + 1.
Example 4
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Constraints
Solution 1: Dynamic Programming
Let us call the function to be computed numSquares(n), which calculates the least number of perfect squares that sum to n.
Here are the findings.
If n is already a perfect square then numSquares(n) = 1.
Otherwise, it could be written as n = 1 + (n-1), or n = 4 + (n-4), or n = 9 + (n-9), etc. which means n is a sum of a perfect square (1, 4 or 9, etc.) and another number m < n. That leads to the problems numSquares(m) of smaller values m.
If you have gotten the results of the smaller problems numSquares(n-1), numSquares(n-4), numSquares(n-9), etc. then numSquares(n) = 1 + the minimum of those results.
Example 4
n = 12 is not a perfect square. It can be written as n = 1 + 11 = 4 + 8 = 9 + 3.
For m = 11, it is not a perfect square and can be written as m = 1 + 10 = 4 + 7 = 9 + 2.
For m = 8, it is not a perfect square and can be written as m = 1 + 7 = 4 + 4 (matched). You get numSquares(8) = 2.
For m = 3, it is not a perfect square and can be written as m = 1 + 2.
You can continue to compute numSquares(m) for other values m in this recursive process. But you can see the case of m = 8 was already the best solution. And numSquares(12) = 1 + numSquares(8) = 1 + 2 = 3, which is the case of n = 12 = 4 + 4 + 4.
To improve runtime, you can apply dynamic programming to cache the numSquares(n) that you have computed.
Code
#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;
int nsq(int n, unordered_map<int, int>& ns) {
auto it = ns.find(n);
if (it != ns.end()) {
return it->second;
}
const int sq = sqrt(n);
if (sq * sq == n) {
ns[n] = 1;
return 1;
}
int result = n;
for (int i = 1; i <= sq; i++) {
result = min(result, nsq(n - i*i, ns));
}
ns[n] = result + 1;
return ns[n];
}
int numSquares(int n) {
unordered_map<int, int> ns;
return nsq(n, ns);
}
int main() {
cout << numSquares(12) << endl;
cout << numSquares(13) << endl;
}
Output:
3
2
Complexity
Runtime: O(n^2).
Extra space: O(n)
Solution 2: Number Theory
The dynamic programming solution above is good enough. But for those who are interested in Algorithmic Number Theory, there is a very interesting theorem that can solve the problem directly without recursion.
It is called Lagrange's Four-Square Theorem, which states
every natural number can be represented as the sum of four integer squares.
It was proven by Lagrange in 1770.
Example 4
n = 12 = 4 + 4 + 4 + 0 or 12 = 1 + 1 + 1 + 9.
Applying to our problem, numSquares(n) can only be 1, 2, 3, or 4. Not more.
It turns into the problem of
identifying when numSquares(n) returns 1, 2, 3, or 4.
Here are the cases.
If n is a perfect square, numSquares(n) = 1.
There is another theorem, Legendre's Three-Square Theorem, which states that numSquares(n) cannot be 1, 2, or 3 if n can be expressed as
n = 4^a(8*b + 7),
where a, b are nonnegative integers. In other words, numSquares(n) = 4 if n is of this form.
Example 3
n = 7 = 4^0(8*0 + 7). It can only be written as 7 = 4 + 1 + 1 + 1.
Code
#include <iostream>
#include <cmath>
using namespace std;
bool isSquare(int n) {
int sq = sqrt(n);
return sq * sq == n;
}
int numSquares(int n) {
if (isSquare(n)) {
return 1;
}
int m = n;
while (m % 4 == 0) {
m /= 4;
}
if (m % 8 == 7) {
return 4;
}
const int sq = sqrt(n);
for (int i = 1; i <= sq; i++) {
if (isSquare(n - i*i)) {
return 2;
}
}
return 3;
}
int main() {
cout << numSquares(12) << endl;
cout << numSquares(13) << endl;
}
Output:
3
2
Complexity
Runtime: O(logn).
Extra space: O(1).
Lagrange's Four-Square Theorem and Legendre's Three-Square Theorem are so powerful to solve this problem. But you can still do a little more algebra to improve further the runtime of the implementation above.
Instead of looping over sqrt(n) in the final for loop, we will prove that this loop over sqrt(m) is enough. That will improve runtime a lot since m is much less than n.
Let m be the reduced value of n after the Legendre's while loop. It satisfies
n = 4^a * m.
We will prove that numSquares(n) = numSquares(m).
In fact, if m is written as m = x^2 + y^2 + z^2, where x, y, z are nonnegative integers. Then
n = 4^a * m = (2^a)^2 * m = (2^a * x)^2 + (2^a * y)^2 + (2^a * z)^2.
In other words, numSquares(n) = numSquares(m).
Now you can change directly the value n during the Legendre's while loop without affecting the final result.
Code
#include <iostream>
#include <cmath>
using namespace std;
bool isSquare(int n) {
int sq = sqrt(n);
return sq * sq == n;
}
int numSquares(int n) {
if (isSquare(n)) {
return 1;
}
while (n % 4 == 0) {
n /= 4;
}
if (n % 8 == 7) {
return 4;
}
const int sq = sqrt(n);
for (int i = 1; i <= sq; i++) {
if (isSquare(n - i*i)) {
return 2;
}
}
return 3;
}
int main() {
cout << numSquares(12) << endl;
cout << numSquares(13) << endl;
}
Output:
3
2
Complexity
Runtime: O(logn).
Extra space: O(1).
Conclusion
The title of this coding challenge (Perfect squares) gives you a hint it is more about mathematics than coding technique.
It is amazing from Lagrange's Four-Square Theorem there are only four possibilities for the answer to the problem. Not many people knowing it.
You can get an optimal solution to a coding problem when you know something about the mathematics behind it.
Hope you learn something from this code challenge.
Have fun with coding and mathematics!
Thanks for reading. Feel free to share your thought about my content and check out my FREE book 10 Classic Coding Challenges.
What is your approach? The problem was picked from leetcode.com. You can submit your solution in any programming language and check the performance.
