grid47 Exploring patterns and algorithms
Sep 4, 2024
5 min read
Solution to LeetCode 633: Sum of Square Numbers Problem
Given a non-negative integer c, determine if there exist two non-negative integers a and b such that a^2 + b^2 = c.
Problem
Approach
Steps
Complexity
Input: You are given a non-negative integer c.
Example: c = 5
Constraints:
• 0 <= c <= 2^31 - 1
Output: Return true if such integers a and b exist, otherwise return false.
Example: true
Constraints:
• The output is either true or false.
Goal: Check if there are two integers a and b such that their squares sum up to the given number c.
Steps:
• Start with two pointers: one at 0 (left) and the other at the square root of c (right).
• Check the sum of their squares: if the sum is less than c, move the left pointer to the right; if it's greater, move the right pointer to the left; if it's equal, return true.
Goal: The function should handle all values of c within the given constraints efficiently.
Steps:
• The value of c is guaranteed to be a non-negative integer.
• The solution must work efficiently even for large values of c, up to 2^31 - 1.
Assumptions:
• The input will always be a valid non-negative integer.
• Input: c = 5
• Explanation: In this case, the integers 1 and 2 satisfy the equation 1^2 + 2^2 = 5, so the output is true.
Approach: The approach uses two pointers to check if there exist two integers whose squares sum up to c.
Observations:
• We need an efficient way to check for the existence of such integers, especially given the large constraint for c.
• Using the two-pointer technique allows us to efficiently check possible pairs of squares without checking every single pair.
Steps:
• 1. Initialize the left pointer at 0 and the right pointer at sqrt(c).
• 2. Iterate while left <= right. Calculate the sum of squares of left and right.
• 3. If the sum is less than c, increment left. If it's greater than c, decrement right. If it's equal to c, return true.
• 4. If no such pair is found, return false.
Empty Inputs:
• The input is always a non-negative integer, so no empty inputs to handle.
Large Inputs:
• Ensure the solution works efficiently even for the largest values of c, up to 2^31 - 1.
Special Values:
• For c = 0, the answer should be true since 0^2 + 0^2 = 0.
Constraints:
• The solution must handle values of c from 0 to 2^31 - 1.
booljudgeSquareSum(int c) {
long left =0, right = sqrt(c);
while(left <= right) {
long res = left * left + right * right;
if(res < c)
left++;
elseif(res > c)
right--;
elsereturntrue;
}
returnfalse;
}
1 : Function Declaration
booljudgeSquareSum(int c) {
This line declares the function `judgeSquareSum`, which takes an integer `c` and returns a boolean value indicating whether `c` can be written as the sum of two squares.
2 : Variable Initialization
long left =0, right = sqrt(c);
Two variables `left` and `right` are initialized. `left` starts at 0, and `right` is set to the square root of `c` (converted to a `long`). These variables will be used to represent the two numbers whose squares are being summed.
3 : Loop
while(left <= right) {
A `while` loop starts, running as long as `left` is less than or equal to `right`. This loop will check different combinations of squares of `left` and `right`.
4 : Sum of Squares Calculation
long res = left * left + right * right;
The sum of squares of `left` and `right` is calculated and stored in the variable `res`.
5 : If Condition for res < c
if(res < c)
If the sum of squares `res` is less than `c`, the left pointer `left` needs to be incremented to increase the sum.
6 : Increment left
left++;
If the sum is less than `c`, the left pointer is incremented to explore larger squares.
7 : Else If Condition for res > c
elseif(res > c)
If the sum of squares `res` is greater than `c`, the right pointer `right` needs to be decremented to reduce the sum.
8 : Decrement right
right--;
If the sum is greater than `c`, the right pointer is decremented to explore smaller squares.
9 : Found Solution
elsereturntrue;
If the sum of squares equals `c`, the function returns `true`, indicating that `c` can be expressed as the sum of two squares.
10 : Return False
returnfalse;
If the loop completes without finding a valid sum of squares, the function returns `false`.
Best Case: O(sqrt(c))
Average Case: O(sqrt(c))
Worst Case: O(sqrt(c))
Description: The time complexity is O(sqrt(c)) because we only need to iterate over the possible values of left and right, which is proportional to the square root of c.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, as we only use a few variables for the pointers and calculation.
