[LeetCode] Sum of Square Numbers

Problem: Given a non-negative integer c, decide whether there're two integers a and b such that a^2 + b^2 = c.

Example:

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

Input: c = 3
Output: false

Input: c = 4
Output: true

Input: c = 2
Output: true

Input: c = 1
Output: true

Approach: If you look at the problem closely, this is similar to the the problem of finding two elements in a sorted array with unique integers whose sum is equal to a given value. 

The sorted array here is the squares of 0,1,2,.....(int)sqrt(c) and the given value is c. We can use the same two pointer approach (one from the start and one from the end) to solve this problem.

Implementation in C#:

    public bool JudgeSquareSum(int c) 

    {

        int start = 0;

        int end = (int)Math.Sqrt(c);        

        while (start <= end)

        {

            int sqrSum = start * start + end * end;

            if (sqrSum == c)

            {

                return true;

            }

            else if (sqrSum < c)

            {

                ++start;

            }

            else

            {

                --end;

            }

        }        

        return false;

    }

Complexity: O(sqrt(c)