LeetCode: Sum of Square Numbers

Posted on January 18, 2018July 26, 2020 by braindenny

Sum of Square Numbers

Similar Problems:

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

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

Example 2:
Input: 3
Output: False

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/sum-of-square-numbers
## Basic Ideas: two pointer
##
##  We can assume a, b non-negative
##
##  0 ... a.. b ..c
##
## Complexity: Time ?, Space ?
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left, right = 0, int(math.sqrt(c))
        while left<=right:
            v = left*left+right*right
            if v == c: return True
            if v>c:
                # make it smaller
                right -= 1
            else:
                left += 1
        return False

Post Views: 8