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

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;
};