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:
-
We initialize two pointers,
l
representing the lower bound and initialized at0
, andr
representing the upper bound and initialized at square root ofc
(sincea
andb
can't be greater than the square root ofc
). -
We keep adjusting these bounds as per the value of
sum
, which isl^2 + r^2
. -
If
sum
is less thanc
, we move the lower boundl
ahead. -
If
sum
is greater thanc
, we move the upper boundr
back. -
If
sum
equalsc
, we returnTrue
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.