633. Sum of Square Numbers

[mah-shamim]

Topics: Math, Two Pointers, Binary Search

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:

• Input: c = 5
• Output: true
• Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

• Input: c = 3
• Output: false

Constraints:

• 0 <= c <= 231 - 1

[basharul-siddike]

We can utilize a two-pointer approach. Here's how we can approach the problem:

Explanation:

1. Constraints:

   • We're given a non-negative integer c.
   • We need to find two integers a and b such that a² + b² = c.

2. Two-pointer Approach:

   • Start with two pointers: a initialized to 0, and b initialized to the square root of c.
   • The idea is to check the sum of the squares of a and b. If a² + b² equals c, return true.
   • If a² + b² is less than c, increment a to increase the sum.
   • If a² + b² is greater than c, decrement b to decrease the sum.
   • Continue this process until a is less than or equal to b.
   • If no such pair is found, return false.

Let's implement this solution in PHP: 633. Sum of Square Numbers

<?php
/**
 * @param Integer $c
 * @return Boolean
 */
function judgeSquareSum($c) {
    // Initialize two pointers
    $a = 0;
    $b = (int) sqrt($c);

    // Iterate while a <= b
    while ($a <= $b) {
        $sumOfSquares = $a * $a + $b * $b;

        if ($sumOfSquares == $c) {
            return true; // Found a pair (a, b)
        } elseif ($sumOfSquares < $c) {
            $a++; // Increment a to increase sum
        } else {
            $b--; // Decrement b to decrease sum
        }
    }

    return false; // No such pair exists
}

// Example usage:
$c1 = 5;
$c2 = 3;

echo "Result for c = $c1: " . (judgeSquareSum($c1) ? "true" : "false") . "\n"; // Output: true
echo "Result for c = $c2: " . (judgeSquareSum($c2) ? "true" : "false") . "\n"; // Output: false
?>

Explanation:

1. Initialization:

   • $a = 0: The left pointer starts from 0.
   • $b = (int) sqrt($c): The right pointer starts from the integer value of the square root of c, as b² cannot exceed c.

2. Loop:

   • The loop continues as long as a <= b.
   • If a² + b² equals c, the function returns true.
   • If a² + b² is less than c, it means we need a larger sum, so we increment a.
   • If a² + b² is greater than c, we need a smaller sum, so we decrement b.

3. End Condition:

   • If no such integers a and b are found, return false.

Time Complexity:

• The time complexity is O(sqrt(c)) because we iterate through the integers from 0 to sqrt(c).

Example Outputs:

• For c = 5, the function will return true because 1² + 2² = 5.
• For c = 3, the function will return false because no integers satisfy the equation a² + b² = 3.

This approach efficiently checks for two integers whose squares sum up to c using a two-pointer technique.

[mah-shamim]

Thanks to solve the problem of checking whether two integers a and b exist such that a² + b² = c

[basharul-siddike]

Thanks