Difficulty:
Related Topics:

Given a non-negative integer ( c ), the task is to determine whether there exist two integers ( a ) and ( b ) such that ( a^2 + b^2 = c ).

We can solve this problem efficiently using a two-pointer technique. The idea is to use one pointer starting from 0 (let's call it low) and another pointer starting from (sqrt{c}) (let's call it high). We then check the sum of squares of the values at these two pointers.

1. Initialize Two Pointers: Set low to 0 and high to ( \sqrt{c} ).
2. Iterate and Check: While low is less than or equal to high, compute the sum of the squares of low and high.
   • If the sum is equal to ( c ), return true.
   • If the sum is less than ( c ), increment the low pointer to increase the sum.
   • If the sum is greater than ( c ), decrement the high pointer to decrease the sum.

class Solution {
public:
    bool judgeSquareSum(int c) {
        int part = 0;
        long long low = 0, high = sqrt(c);

        while (low <= high) {
            long long sumOfSquares = low * low + high * high;
            if (sumOfSquares == c) {
                return true;
            } else if (sumOfSquares > c) {
                high--;
            } else {
                low++;
            }
        }

        return false;
    }
};

Initialization:

• low is initialized to 0.
• high is initialized to ( \sqrt{c} ).

Iteration:

• The while loop continues as long as low is less than or equal to high.
• In each iteration, we calculate sumOfSquares as ( \text{low}^2 + \text{high}^2 ).
  • If sumOfSquares is equal to ( c ), we return true indicating that such integers ( a ) and ( b ) exist.
  • If sumOfSquares is greater than ( c ), we decrement high to reduce the sum.
  • If sumOfSquares is less than ( c ), we increment low to increase the sum.

Termination:

• If the loop exits without finding any such pairs, we return false.

Efficiency:

• The two-pointer approach iterates at most ( \sqrt{c} ) times, making the time complexity ( O(\sqrt{c}) ). This is an optimal and efficient solution for the problem.

If you found this solution helpful, please consider liking 👍 and upvoting ⬆️. Your support helps in continuing to provide high-quality solutions.