LeetCode: Sum of Square Numbers Posted on January 18, 2018July 26, 2020 by braindenny Sum of Square Numbers Similar Problems: Series: TwoSum Problems & Follow-Up LintCode: 3Sum II CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #math, #twopointer, #sqrt, #twosum 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