Sum Of Square Numbers - Leetcode Solution

Problem Statement:

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

Example 1:

Input: 5

Output: True

Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3

Output: False

Solution:

In this problem, we are given a non-negative integer 'c' and we have to find out whether there are two integers 'a' and 'b' such that a^2 + b^2 = c. There are multiple approaches to solving this problem. Let's discuss some of them.

Using Two Pointers:

We can use the two-pointer technique to search for the two numbers 'a' and 'b' such that a^2 + b^2 = c. Since the input 'c' is non-negative, the highest number 'b' can be is the square root of 'c'. We start with 'a' = 0 and 'b' = sqrt(c). We keep incrementing 'a' until a^2 + b^2 < c. At this point, we increment 'b' and repeat the process until a^2 + b^2 = c or a >= b.

Let's see how this approach can be implemented in code:

class Solution: def judgeSquareSum(self, c: int) -> bool: a, b = 0, int(math.sqrt(c)) while a <= b: cur_sum = a * a + b * b if cur_sum == c: return True elif cur_sum < c: a += 1 else: b -= 1 return False

Time Complexity: O(sqrt(c)).

Using Binary Search:

We can also use binary search to find the two numbers 'a' and 'b' such that a^2 + b^2 = c. We fix one of the numbers to be 'a' and search for the second number 'b' using binary search in the range [0, sqrt(c)]. We initialize the left and right indexes of the range and the middle index as 0 and sqrt(c), respectively. We calculate the sum of squares of middle index and 'a'. If the sum is equal to 'c', we return True. If the sum is less than 'c', we increase the left index. If the sum is greater than 'c', we decrease the right index. We repeat this process until the left index becomes greater than the right index.

Let's see how this approach can be implemented in code:

class Solution: def judgeSquareSum(self, c: int) -> bool: for a in range(int(math.sqrt(c)) + 1): left, right = a, int(math.sqrt(c - a * a)) while left <= right: mid = left + (right - left) // 2 cur_sum = a * a + mid * mid if cur_sum == c: return True elif cur_sum < c: left = mid + 1 else: right = mid - 1 return False

Time Complexity: O(sqrt(c) x log(sqrt(c))).

Using Fermat's Theorem:

We can also use Fermat's theorem to solve this problem efficiently. The theorem states that every positive integer can be expressed as the sum of at most three squares. Therefore, we can check whether 'c' can be expressed as the sum of two squares by iterating 'a' from 0 to sqrt(c) and checking whether sqrt(c - a^2) is an integer.

Let's see how this approach can be implemented in code:

class Solution: def judgeSquareSum(self, c: int) -> bool: for a in range(int(math.sqrt(c)) + 1): b = int(math.sqrt(c - a * a)) if a * a + b * b == c: return True return False

Time Complexity: O(sqrt(c)).

Overall, the time complexity of these solutions is the same. However, the three-pointer approach is the easiest to understand and implement.

1