Leetcode 633. Sum of Square Numbers

Problem Explanation

Given a non-negative integer c, we ought to determine whether there are two integers a and b such that the sum of their squares is equal to c. In other words, we need to check if there exist integers a and b satisfying the equation a^2 + b^2 = c.

Let's observe an example for better understanding:

Example

Suppose our input is c = 5. If we attempt to find two numbers, a and b, such that a^2 + b^2 = c, we might come up with the pair (1, 2) because 1^2 + 2^2 = 1 + 4 = 5, which is our input number. So, in this case, the output would be True, indicating that such a pair of integers do exist.

Approach

Our approach in the given solution is fairly straightforward:

  1. We initialize two pointers, l representing the lower bound and initialized at 0, and r representing the upper bound and initialized at square root of c (since a and b can't be greater than the square root of c).

  2. We keep adjusting these bounds as per the value of sum, which is l^2 + r^2.

  3. If sum is less than c, we move the lower bound l ahead.

  4. If sum is greater than c, we move the upper bound r back.

  5. If sum equals c, we return True representing that we've found the pair of integers.

If our pointers cross each other and the loop terminates without finding the pair, we return False.

Python Solution

1
2python
3import math
4
5class Solution:
6    def judgeSquareSum(self, c: int) -> bool:
7        l = 0
8        r = int(math.sqrt(c))
9
10        while l <= r:
11            sum = l*l + r*r
12            if sum == c:
13                return True
14            elif sum < c:
15                l += 1
16            else:
17                r -= 1
18
19        return False

Java Solution

1
2java
3class Solution {
4    public boolean judgeSquareSum(int c) {
5        int l = 0;
6        int r = (int) Math.sqrt(c);
7
8        while (l <= r) {
9            int sum = l * l + r * r;
10            if (sum == c) {
11                return true;
12            } else if (sum < c) {
13                l++;
14            } else {
15                r--;
16            }
17        }
18        
19        return false;
20    }
21}

JavaScript Solution

1
2javascript
3var judgeSquareSum = function(c) {
4    let l = 0;
5    let r = ~~Math.sqrt(c);
6
7    while (l <= r) {
8        let sum = l * l + r * r;
9        if (sum === c) {
10            return true;
11        } else if (sum < c) {
12            l++;
13        } else {
14            r--;
15        }
16    }
17
18    return false;
19};

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool judgeSquareSum(int c) {
6        long l = 0, r = sqrt(c);
7        while (l <= r) {
8            long sum = l * l + r * r;
9            if (sum == c) {
10                return true;
11            } else if (sum < c) {
12                l++;
13            } else {
14                r--;
15            }
16        }
17        return false;
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public bool JudgeSquareSum(int c) {
5        int l = 0;
6        int r = (int)Math.Sqrt(c);
7        while (l <= r) {
8            int sum = l * l + r * r;
9            if (sum == c) {
10                return true;
11            } else if (sum < c) {
12                l++;
13            } else {
14                r--;
15            }
16        }
17        return false;
18    }
19}

By maintaining two pointers and moving them based on the comparison of current sum with c, we ensure that every possible combination of a and b within the bounds of 0 and sqrt(c) is checked. This approach makes the problem solution achievable in O(sqrt(c)), time complexity wise.# Python Solution Explained

The Python solution begins with the importation of the math module, this is to acquire the math.sqrt() method which is able to calculate the square root of the integer c.

A class is initialized, named Solution, and within it there's a method named judgeSquareSum. It takes in c as an argument, which is the sum of the squares of two numbers we need to find.

In the method, l is initialized with 0 representing the lower bound and r initialized as the square root of c representing the upper bound.

A while loop is then created, where the loop continues until l is greater than r. Within the loop, a sum variable is calculated as the sum of the squares of the values of l and r. If the sum matches c, it returns True. However, if the sum is less than c, l is incremented and if the sum is greater than c, r is decremented.

Finally, if no such pair of a and b is found where a^2 + b^2 = c, the function returns False.

Java, JavaScript, C++ and C# Solutions Explained

All the solutions in Java, JavaScript, C++, and C# follow the same logic as explained above with the Python solution. However, the syntax is specific to each language.

For instance, in the Java solution, Math.sqrt(c) is used to calculate the square root, and in the JavaScript solution, Math.sqrt(c) is 'floored' using the ~~ notation to ensure it's an integer.

In the C++ solution, long data types are used which fits for this problem because C++'s int data type might not support values of size above 2^31-1.

In the C# solution, Math.Sqrt(c) method is used to calculate the square root and type conversion is handled internally.

These solutions use a two-pointer approach to progressively narrow down the possibilities of the pairs (a, b), which reduces the time complexity to the square root of c(i.e., O(sqrt(c))). The space complexity for all these solutions is O(1), as no additional data structures have been used.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫