Before we start, I want to confirm that all the returned values will always be in range [1,4] inclusively. Why is that? It is because we have Lagrange's Four Square Theorem, also known as Bachet's conjecture:
Every natural numbers can be expressed as a sum of four square numbers. (*)
The theorem is proved by Lagrange in 1770. To understand the proof, I suggest you read the provided link from Wiki. And later, the talented mathematician Ramanujan did a generalization on the theorem. I have to say it is extremely sad that Ramanujan's life was too short, even though his legacy is more than 3900 results (mostly identities and equations).
As a note, many proofs of the theorem use the Euler's four square identity:
Picture 1: Euler's Four Square Identity
Now I suggest you read this page. After reading it, you can solve this LeetCode problem mathematically! And you can also understand the algorithm to represent a natural number as a sum of four perfect squares!
Let me help you to summarize the related part of it.
From the article, you can find that if a number is in the form n = 4^r (8k+7) (Where ^ is power), then n cannot be represented as a sum of less than 4 perfect squares. If n is not in the above form, then n can be represented as a sum of 1, 2, or 3 perfect squares.
So now you know the basic theory behind, we can start coding!
I. Python Code
class Solution(object):
def is_square(self, n):
temp = int(math.sqrt(n))
return temp*temp == n
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
while n & 3 == 0: #n % 4
n = n >> 2
if n % 8 == 7: return 4
sqrt_n = int(math.sqrt(n))
if self.is_square(n): return 1
else:
for i in range(1, sqrt_n+1):
if self.is_square(n-i*i):
return 2
return 3
II. Java Code
public class Solution {
public boolean is_square(int n){
int temp = (int) Math.sqrt(n);
return temp * temp == n;
}
public 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) Math.sqrt(n);
for (int i = 1; i<= sqrt_n; i++){
if (is_square(n-i*i)) return 2;
}
return 3;
}
}
III. C++ Code
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;
}
};
IV. Javascript Code
/**
* @param {number} n
* @return {number}
*/
var is_square = function(n){
var t = Math.floor(Math.sqrt(n));
return t * t == n;
}
var numSquares = function(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;
var sqrt_n = Math.floor(Math.sqrt(n));
for(var i=1; i<= sqrt_n; i++){
if(is_square(n-i*i)) return 2;
}
return 3;
};
