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:

Image of Datadog

Master Mobile Monitoring for iOS Apps

Monitor your app’s health with real-time insights into crash-free rates, start times, and more. Optimize performance and prevent user churn by addressing critical issues like app hangs, and ANRs. Learn how to keep your iOS app running smoothly across all devices by downloading this eBook.

Get The eBook

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →