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 Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay