DEV Community

Cover image for 633. Sum of Square Numbers
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

633. Sum of Square Numbers

633. Sum of Square Numbers

Difficulty: Medium

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

Solution:

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) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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
?>
Enter fullscreen mode Exit fullscreen mode

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 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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more