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:

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs