LeetCode 633.

Intuition

a^2 + b^2 = c; (a >= 0 & b >= 0 & a,b,c are integers)

Simply get the constraints: a,b <= sqrt(c)

Approach

Iterate a,b from 0 to sqrt(c). Be careful to the limit of integer 2^31 - 1.

As a result, use subtraction instead of addition.

Complexity

• Time complexity: O(n)

• Space complexity: O(1)

Code

class Solution {
    public boolean judgeSquareSum(int c) {
        int init = (int) Math.sqrt(c);
        int tmp = 0, tmp1 = 0;
        for (int i=0; i <= init; i++) {
            tmp = c - i*i;
            tmp1 = (int) Math.sqrt(tmp);
            if (tmp == tmp1 * tmp1) {
                return true;
            }
        }
        return false;
    }
}

Check out the description of this problem at LC 633.