Leetcode 633: Sum of Square Numbers

Problem Description

#

Check out the problem on Leetcode

Given a non-negative integer \(c\), decide whether there exists two integers \(a\) and \(b\) such that \(a^2+b^2=c\)

Solution

#

Try different combinations of \((a,b)\), adjusting the guess each time based on whether their sum is too large or too small. I define \(a\) as the smaller value and \(b\) as the larger value.

Initial values

#

• \(a=0\)
• \(b^2>=c\)
• \(\text{sum}=b^2\)

Finding the solution

#

If the sum is too big, then make \(b\) smaller. If it is too large, make \(a\) larger. Stop when \(a>b\).

Optimising sum calculation

#

\((a+1)^2 = a^2+2a+1\)

\((b-1)^2 = b^2-2b+1\)

We can use this to update sum:

\((a+1)^2+b^2 = a^2+2a+1+b^2\)

\( \quad \quad \quad \quad \quad \ \ \ = \text{sum} + 2a + 1\)

Therefore, instead of recalculating the sum each time using a*a+b*b, we can instead use these formulae. For example, if increasing a, sum += 2a+1.

Complexity

#

• Time complexity: O(\(\sqrt{n}\) )

• Space complexity: O(1)

Code

#

bool judgeSquareSum(const int& c) {
    // let a<=b
    unsigned int a = 0;
    unsigned int b = ceil(sqrt(c));
    unsigned int sum = b*b;
    while(a<=b){
        if(sum==c){
            return true;
        }
        else if(sum<c){
            // increase a
            // (a+1)^2 = a^2 +2a+1
            sum += 2*a+1;
            a++;
        }
        else{
            // decrease b
            // (b-1)^2 = b^2-2b+1
            sum += 1-2*b;
            b--;
        }
    }
    return false;
}