Leetcode（633）—— Sum of squares

subject

Given a nonnegative integer c , You have to decide if there are two integers a and b, bring $a^2+b^2=c$.

Example 1：

Input ：c = 5
Output ：true
explain ：1 * 1 + 2 * 2 = 5

Example 2：

Input ：c = 3
Output ：false

Tips ：

• $0$ <= c <= $2^{31-1}$

Answer key

​​   For a given nonnegative integer $c$, You need to determine whether there is an integer $a$ and $b$, bring $a^2+b^2=c$. You can enumerate $a$ and $b$ All possible situations , The time complexity is $O(c^2)$. But there are some situations where violence is unnecessary . for example ： When $c=20$ when , When $a=1$ When , enumeration $b$ When , Just enumerate to $b=5$ And that's it , This is because $1^2+5^2=25>20$. When $b>5$ when , There must be $1^2+b^2>20$.

​​   Take note of this , have access to $\text{sqrt}$ Functions or double pointers reduce time complexity .

Method 1 ： Using standard library functions $\text{sqrt}$

Ideas

​​   In enumeration $a$ At the same time , Use $\text{sqrt}$ Function to find $b$. Be careful ： This topic $c$ The value range of is $[0,2^{31}-1]$, Therefore, in the process of calculation, it may happen $\text{int}$ Type overflow , Need to use $\text{long}$ Type to avoid overflow .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    bool judgeSquareSum(int c) {
    
        for (long a = 0; a * a <= c; a++) {
    
            double b = sqrt(c - a * a);
            if (b == (int)b) {
    
                return true;
            }
        }
        return false;
    }
};

Complexity analysis

Time complexity ：$O(\sqrt{c})$. enumeration $a$ The time complexity of is $O(\sqrt{c})$, For each $a$ Value , Can be found in $O(1)$ Time to find $b$
Spatial complexity ：$O(1)$

Method 2 ： Reverse double pointer

Ideas

​​   No loss of generality , It can be assumed $i\le max$. At the beginning $i=0$,$max=\sqrt{c}$, Do the following ：

• If $ma{x}^2+i^2=c$, We found a solution to the problem , return $\text{true}$;
• If $ma{x}^2+i^2<c$, At this time, we need to $i$ The value of the add $1$, Continue to find ;
• If $ma{x}^2+i^2>c$, At this time, we need to $max$ The value of the reduction $1$, Continue to find .
• When $max=i$ when , Find the end , At this point, if the integer is still not found $max$ and $i$ Satisfy $ma{x}^2+i^2=c$, Then there is no solution required by the problem , return $\text{false}$.

​​   As for the correctness of reverse double pointer traversing the sorted sequence （ That is, how to ensure that the correct answer is not missed ）： You can refer to here .
​​   So there are two issues to consider when using reverse double pointers ： Each time the pointer is moved, what conditions are eliminated ？ Are these situations likely to contain the correct answer ？

Code implementation

my ：

class Solution {
    
public:
    bool judgeSquareSum(int c) {
    
        //  Find out that the square root is less than or equal to  c  Maximum integer for  max
        int max = sqrt(c), i = 0;
        while(i <= max){
    
            //  no need  max*max + i*i  and  c  Compare , Because type overflow may occur 
            if(c - max*max == i*i) return true;
            c - max*max < i*i? max--: i++;
        }
        return false;
    }
};

Complexity analysis

Time complexity ：$O(\sqrt{c})$. In the worst case $max$ and $i$ A total of $0$ To $\sqrt{c}$ All integers in .
Spatial complexity ：$O(1)$

Method 3 ： mathematics

Ideas

​​   Fermat's sum of squares theorem tells us ：

A nonnegative integer $c$ If it can be expressed as the sum of the squares of two integers , If and only if $c$ All of the forms of $4k+3$ The powers of the prime factors of are even .

Certificate see here .

​​   So we need to be right about $c$ Do prime factor decomposition , Then judge all shapes such as $4k+3$ Whether the powers of the prime factors of are all even numbers .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    bool judgeSquareSum(int c) {
    
        for (int base = 2; base * base <= c; base++) {
    
            //  If it's not a factor , Enumerate the next 
            if (c % base != 0) {
    
                continue;
            }

            //  Calculation  base  The power of 
            int exp = 0;
            while (c % base == 0) {
    
                c /= base;
                exp++;
            }

            //  according to  Sum of two squares theorem  verification 
            if (base % 4 == 3 && exp % 2 != 0) {
    
                return false;
            }
        }

        //  for example  11  Such use cases , Because of the above  for  In circulation  base * base <= c ,base == 11  It doesn't enter the circulation body 
        //  Therefore, it is necessary to make another judgment after exiting the loop 
        return c % 4 != 3;
    }
};

Complexity analysis

Time complexity ：$O(\sqrt{c})$
Spatial complexity ：$O(1)$