“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Sum of squares of training algorithm

Today we are going to learn a number calculation algorithm problem 633 on LeetCode. Friends can do it themselves first.

Square number sum of leetcode portal

The title

Given a non-negative integer c, you need to determine whether there are two integers A and b such that a^2 + b^2 =c.

Given a non-negative integer c, decide whether there’re two integers a and b such that a2 + b2 = c.

Ecample:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Input: c = 4
Output: true
Explanation: 0 * 0 + 2 * 2 = 4
Copy the code

The problem solving

  1. We can enumerate a (0<= a <= math.sqrt (c)). And then check to see if there’s an integer b that makes this equation true.

    / * * *@param {number} c
 * @return {boolean}* /
var judgeSquareSum = function(c) {
    for(let i = 0; i <= Math.floor(Math.sqrt(c)); i ++) {
        const   b = Math.sqrt(c - i * i);
        if(b === parseInt(b)) return true;
    }
    return false;
};
Copy the code

  2. The range of a and B must be between [0, math.sqrt (c)]. We can also use double Pointers to narrow the range of a and B values until the true result is found. Or if a smaller value is found but no larger value is found, return false.

    / * * *@param {number} c
 * @return {boolean}* /
var judgeSquareSum = function(c) {
    let a = 0; b  = Math.floor(Math.sqrt(c));
    while(a <= b) {
        if(a **2 + b **2 === c) return true;
        if(a **2 + b **2 < c) a++;
        if(a **2 + b **2 > c) b--;
    }
    return false;
};
Copy the code
    1. Sum of Fermat squares

    Fermat’s sum of squares theorem: A non-negative integer C can be expressed as the sum of squares of two integers if and only if the powers of the prime factors of C, such as 4K +3, are even. According to this theorem a solution can be obtained

    / * * *@param {number} c
 * @return {boolean}* /
var judgeSquareSum = function(c) {
    for(let i = 2; i <= Math.floor(Math.sqrt(c)); i ++) {
        if(c % i ! = =0) {
            continue; // Not a factor, next
        }

        let exp = 0;
        while(c % i ===0) { // Compute the power of I
            c/= i;
            exp ++;
        }
        if(i % 4= = =3 && exp %2! = =0) { // Verify according to the sum of squares theorem
            return false; }}return c % 4! = =3;
};
Copy the code

    Ok, this is all the content of today’s brush questions, have you learned?