Perfect Squares [LeetCode] Part 2: Solve it Mathematically

This is continuation of the previous post - Perfect Squares. I've decided to separate the problem into two parts because the solution using maths knowledge recalled me the happy time when I studied maths in high school.

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

view plainprint?

1. class Solution(object):  
2.       
3.     def is_square(self, n):  
4.         temp = int(math.sqrt(n))  
5.         return temp*temp == n  
6.           
7.     def numSquares(self, n):  
8.         """ 
9.         :type n: int 
10.         :rtype: int 
11.         """  
12.         while n & 3 == 0: #n % 4  
13.             n = n >> 2  
14.         if n % 8 == 7: return 4  
15.           
16.         sqrt_n = int(math.sqrt(n))  
17.         if self.is_square(n): return 1  
18.         else:  
19.             for i in range(1, sqrt_n+1):  
20.                 if self.is_square(n-i*i):  
21.                     return 2  
22.         return 3  

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

view plainprint?

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

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

view plainprint?

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

IV. Javascript Code

view plainprint?

1. /** 
2.  * @param {number} n 
3.  * @return {number} 
4.  */  
5. var is_square = function(n){  
6.     var t = Math.floor(Math.sqrt(n));  
7.     return t * t == n;  
8. }  
9. var numSquares = function(n) {  
10.     while ((n & 3) ===0) //n%4 == 0  
11.         n >>=2;  
12.     if((n&7) == 7) return 4; //n % 8 = 7  
13.     if(is_square(n)) return 1;  
14.     var sqrt_n = Math.floor(Math.sqrt(n));  
15.     for(var i=1; i<= sqrt_n; i++){  
16.         if(is_square(n-i*i)) return 2;  
17.     }  
18.     return 3;  
19. };  

/**
 * @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;
};