Python, Straightforward with Explanation


  • 8
    def judgeSquareSum(self, c):
        def is_square(N):
            return int(N**.5)**2 == N
            
        return any(is_square(c - a*a) 
                    for a in xrange(int(c**.5) + 1))
    

    Without loss of generality, let's consider only a, b >= 0. This is because if say, a < 0, then we may also find a solution using abs(a).

    Now, a*a = c - b*b <= c, because b*b >= 0, and 0 <= a <= sqrt(c) is a necessary condition for a solution.

    Let's try each 0 <= a <= sqrt(c). For each choice of a, we must have b*b = c - a*a. There will be a solution if and only if the right-hand-side is a perfect square.


  • 0
    S

    a can be further constrained by a*a <= c/2. If there is no solution in this range for a, then there cannot be a solution when c/2 < a*a <= c.
    Proof: if there is one solution with a * a > c/2, then the corresponding b must satisfy b * b <= c/2. Consequently, the solution (b, a) should have already been found.

    #include <cmath>
    class Solution {
    public:
        bool judgeSquareSum(int c) {
            auto end = (int)std::sqrt(c / 2.0);
            for (int a = 0; a <= end; a++){
                auto bs = c - a * a; // b^2
                auto b = (int)std::sqrt(bs);
                if (b * b == bs)
                    return true;
            }
            return false;
        }
    };

  • 0
    H
    This post is deleted!

  • 0

    @HongxiangWang 1*1 + 1*1 = 2


  • 0
    H

    @awice Oh, thanks!


Log in to reply
 

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