633. Sum of Square Numbers
Problem Description
The problem is about determining if it's possible to find two non-negative integers a
and b
, such that when you square each of them and add them together, the result is equal to a given non-negative integer c
. This can be expressed with the equation a^2 + b^2 = c
. You are required to check if there exists at least one pair (a, b)
that satisfies this equation for the given c
.
Intuition
The intuition behind the solution is based on the properties of a right-angled triangle where the squares of the two shorter sides sum up to the square of the longest side (Pythagorean theorem). In this problem, the non-negative integers a
and b
are similar to the two shorter sides, and c
is like the square of the longest side.
The solution approach is inspired by binary search, which is typically used to find an element in a sorted array. Rather than searching through all possible pairs of a
and b
, which would be inefficient, the algorithm starts with two potential candidates: a
starting from 0 and b
from the square root of c
, since b
can't be larger than sqrt(c)
if b^2
is to stay less than or equal to c
.
The while loop then examines the sum of squares of a
and b
. If the sum equals c
, the answer is True
. If the sum is less than c
, a
is incremented to increase the sum, exploring the possibility of larger a^2
contributions. If the sum is greater than c
, b
is decremented to decrease the sum, as b
might be too large.
This searching process ends when a
becomes greater than b
because, at that point, all pairs that could potentially add up to c
have already been tested. If no such pair has been found by then, the algorithm returns False
, indicating no such pair exists for the given c
.
Learn more about Math, Two Pointers and Binary Search patterns.
Solution Approach
The implementation uses a two-pointer technique that starts with the two pointers at the minimal and maximal possible values of a
and b
that could satisfy the equation a^2 + b^2 = c
. Pointer a
starts from 0, as it represents the smallest possible square contributing to c
. Pointer b
starts from int(sqrt(c))
, which is the largest integer that when squared does not exceed c
.
The algorithm's core logic is a loop that continues to execute as long as a
is less than or equal to b
. During each iteration, it computes the sum s
of the squares of a
and b
. This sum s = a^2 + b^2
is then compared to the target sum c
:
- If
s
is equal toc
, then we know that such a pair(a, b)
exists, and the function immediately returnsTrue
. - If
s
is less thanc
, the sum is too small, anda
is incremented by 1 to try a larger value fora^2
. - If
s
is greater thanc
, the sum is too large, andb
is decremented by 1 to try a smaller value forb^2
.
The loop continues this process, incrementing a
or decrementing b
as necessary, stopping when a
exceeds b
. If the loop concludes without finding a matching pair, the function returns False
, indicating there are no two perfect square numbers that add up to c
.
This algorithm follows an approach similar to a binary search, as the reference approach indicates, where instead of searching in a sorted array, it "searches" through a conceptualized sorted space of squared numbers, moving one of the boundaries (either a
or b
) closer to a potential solution at each step.
The reason why the algorithm stops once a
exceeds b
is because we're dealing with non-negative integers, and squares of integers grow very quickly. Once a > b
, the possible sums of squares will no longer decrease (since a^2
is now greater than b^2
), which means we can be certain no subsequent iterations will result in the sum c
.
The efficiency and elegance of this solution lie in its O(sqrt(c)) time complexity, as b
is reduced from sqrt(c)
to 0 in the worst case, and a
is increased from 0 to sqrt(c)
in the worst case. This is much more efficient than a brute-force approach that would be O(c), where we would have to check every pair (a, b)
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's work through a small example with c = 5
.
Initially, we start with two pointers for a
and b
such that:
a
starts from0
, as it represents the smallest possible square contributing toc
.b
starts fromint(sqrt(c))
, which is2
in our example because2^2 = 4
is the largest square less than or equal toc
.
Now, let's begin the process:
-
In the first iteration, the sum of squares
s
will bea^2 + b^2 = 0^2 + 2^2 = 0 + 4 = 4
. Sinces
is less thanc
, we need to increasea
. We incrementa
to1
. -
In the second iteration,
s
will bea^2 + b^2 = 1^2 + 2^2 = 1 + 4 = 5
, which is exactly equal toc
. At this point, we have found that the pair(a, b) = (1, 2)
satisfies the equationa^2 + b^2 = c
. The algorithm returnsTrue
.
In this example, we found that c
can indeed be expressed as the sum of two squared integers. The algorithm works efficiently and quickly identifies the correct pair without needing to check every single possibility.
If we had a larger c
where no squares add up to c
, the algorithm would continue incrementing a
and decrementing b
until a
surpasses b
. If no valid pair is found by the time a
exceeds b
, the algorithm will return False
, indicating no such pair exists for the given c
.
Solution Implementation
1from math import sqrt
2
3class Solution:
4 def judgeSquareSum(self, target: int) -> bool:
5 # Initialize two pointers. `left` starts at 0, and `right` starts at the square root of target,
6 # truncated to an integer, which is the largest possible value for a or b if a^2 + b^2 == target.
7 left, right = 0, int(sqrt(target))
8
9 # Loop until the two pointers meet
10 while left <= right:
11 # Calculate the sum of squares of the two pointers
12 current_sum = left ** 2 + right ** 2
13
14 # If the sum equals the target, we found a solution
15 if current_sum == target:
16 return True
17 # If the sum is less than the target,
18 # increment the left pointer to try a larger square for `a^2`
19 elif current_sum < target:
20 left += 1
21 # If the sum is greater than the target,
22 # decrement the right pointer to try a smaller square for `b^2`
23 else:
24 right -= 1
25
26 # If no pair of squares was found that sums up to the target, return False
27 return False
28
29# Example usage:
30# solution = Solution()
31# print(solution.judgeSquareSum(5)) # Output: True
32# print(solution.judgeSquareSum(3)) # Output: False
33
1class Solution {
2 public boolean judgeSquareSum(int c) {
3 // Initialize two pointers. 'smallest' starts at 0 and 'largest' starts at the square root of 'c'
4 long smallest = 0;
5 long largest = (long) Math.sqrt(c);
6
7 // Use a two-pointer approach to find if there exist two numbers 'a' and 'b'
8 // such that a^2 + b^2 equals to 'c'
9 while (smallest <= largest) {
10 // Calculate the sum of squares of 'smallest' and 'largest'
11 long sumOfSquares = smallest * smallest + largest * largest;
12
13 // Check if the current sum of squares equals to 'c'
14 if (sumOfSquares == c) {
15 // If yes, then we found that 'c' can be expressed as a sum of squares.
16 return true;
17 }
18
19 // If the sum of squares is less than 'c', we increment 'smallest' to get a larger sum
20 if (sumOfSquares < c) {
21 ++smallest;
22 } else {
23 // If the sum of squares is greater than 'c', we decrement 'largest' to get a smaller sum
24 --largest;
25 }
26 }
27
28 // If we exit the loop, then there are no such 'a' and 'b' that satisfy a^2 + b^2 = 'c'
29 return false;
30 }
31}
32
1class Solution {
2public:
3 // This method checks if the input 'c' can be expressed as the sum of squares of two integers.
4 bool judgeSquareSum(int c) {
5 // Start one pointer 'a' from the smallest possible square, 0.
6 long a = 0;
7 // Start another pointer 'b' from the largest possible square that is less than or equal to 'c'.
8 long b = static_cast<long>(sqrt(c));
9
10 // Continue the search as long as 'a' is less than or equal to 'b'.
11 while (a <= b) {
12 // Calculate the sum of the squares of 'a' and 'b'.
13 long sumOfSquares = a * a + b * b;
14
15 // If the sum equals to 'c', we found the two numbers whose squares sum up to 'c'.
16 if (sumOfSquares == c) return true;
17
18 // If the sum is less than 'c', then we need to increase 'a' to get a larger sum.
19 if (sumOfSquares < c)
20 ++a;
21 // If the sum is greater than 'c', we need to decrease 'b' to get a smaller sum.
22 else
23 --b;
24 }
25
26 // If no pair of integers has been found whose squares sum up to 'c', return false.
27 return false;
28 }
29};
30
1// This function checks if a given number c can be written as the sum
2// of the squares of two integers (c = a^2 + b^2).
3function judgeSquareSum(c: number): boolean {
4 // Starting with a at the smallest square (0) and b at the largest
5 // square not greater than the square root of c.
6 let a = 0;
7 let b = Math.floor(Math.sqrt(c));
8
9 // Loop until a and b meet or cross each other.
10 while (a <= b) {
11 // Calculating the sum of squares of both a and b.
12 let sumOfSquares = a ** 2 + b ** 2;
13
14 // If the sum of squares is equal to c, we found a valid pair.
15 if (sumOfSquares == c) {
16 return true;
17 }
18
19 // If the sum of squares is less than c, we need to try a larger value of a.
20 if (sumOfSquares < c) {
21 ++a; // Increment a to increase the sum.
22 } else {
23 --b; // Decrement b to decrease the sum.
24 }
25 }
26
27 // If we exit the loop, no valid pair was found that fulfills the condition.
28 return false;
29}
30
Time and Space Complexity
The time complexity of the given code is O(sqrt(c))
because the while loop runs with a
starting from 0
and b
starting from int(sqrt(c))
, moving closer to each other with each iteration. The loop terminates when a
exceeds b
, and since b
decrements with a magnitude that is at most the square root of c
(as that is its starting value), we can bound the number of iterations by 2*sqrt(c)
(since both a
and b
can move sqrt(c)
times at most).
The space complexity of the code is O(1)
because the space used does not scale with the value of c
. Only a constant amount of additional memory is used for the variables a
, b
, and s
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Want a Structured Path to Master System Design Too? Don’t Miss This!