Sum of Square Numbers

Problem

Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: 3
Output: False

Solution

Two Pointers Solution: O(sqrt(n)) time, O(1) space

public class Solution {
    public boolean judgeSquareSum(int c) {
        int low = 0, high = sqrt(c);
        while (low <= high) {
            int sum = low * low + high * high;
            if (sum == c) return true;
            if (sum < c) low++;
            else high--;
        }
        return false;
    }

    //Implementation of Sqrt() method using Binary Search 
    private int sqrt(int num) {
        int i = 0, j = num / 2 + 1;
        while (i <= j) {
            long mid = (i + j) / 2;
            long square = mid * mid;
            if (square == num) return mid;
            if (square < num) i = mid + 1;
            else j = mid - 1; //if given num is not a square number, will reach this line
        }
        return 0;
    }
}

Analysis

We have two pointers low = 0 and high = sqrt(c)
Then as long as low <= high we get their sum and compare to given number c
We update the low and high based on the result of comparison
Notice how sqrt() method is implemented if Math.sqrt() is not allowed during the interview