O(nlogn) time and O(1) space binary search solution.


  • 0
    M

    The idea is to find a number b, which b^2 == c - a^2 . If b exists, return true. Otherwise return false. This question now becomes to judge if a number has an integer root.

    Note that neither abs(a) or abs(b) should be greater than sqrt(c) , otherwise we just return false.

    It's not neccessary to count negative integers in for a and b because (-2)^2 == (2)^2. We can just start from 0.

    class Solution {
    public:
        bool judgeSquareSum(int c) {
            int r = sqrt(c);
            if (r * r == c)
            {
                return true;
            }
            
            for (int i = r; i >= 0; --i)
            {
                if (isSquarable(c - i * i))
                {
                    return true;
                }
            }
            
            return false;
        }
        
    private:
        bool isSquarable(int c)
        {
            int r = sqrt(c);
            if (r * r == c)
            {
                return true;
            }
            
            int b = 0;
            int e = r;
            
            while (b <= e)
            {
                int m = b + (e - b) / 2;
                
                if (m * m == c)
                {
                    return true;
                }
                
                if (m * m < c)
                {
                    b = m + 1;
                }
                else
                {
                    e = m - 1;
                }
            }
            
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.