633. Sum of Square Numbers

MediumView on LeetCode

Math Binary Search Two Pointers

Time: O(√c)

Space: O(1)

Intuition

Two-pointer: set lo=0, hi=floor(sqrt(c)). Check lo²+hi²==c, adjust pointers.

Algorithm

1lo = 0, hi = (int)sqrt(c).
2While lo <= hi: compute sum = lo²+hi². If sum==c return true. If sum<c lo++. Else hi--.

Common Pitfalls

•Use long arithmetic to avoid overflow when squaring. lo can equal hi (same number twice).

633.cs

// Approach: Two pointers starting at 0 and sqrt(c); advance left if sum too
// small and retreat right if too large.
// Time: O(√c) Space: O(1)

public class Solution {
    public bool JudgeSquareSum(int c) {
        long l = 0;
        long r = (long)Math.Sqrt(c);

        while(l <= r)
        {
            long sum = (l * l) + (r * r);
            if(sum == c)
                return true;
            else if(sum < c)
                l++;
            else
                r--;
        }

        return false;
    }
}

Was this solution helpful?