algoadvance

Leetcode 633. Sum of Square Numbers

Problem Statement

Given a non-negative integer c, determine whether there are two integers a and b such that:

[ a^2 + b^2 = c ]

Return true if such a pair exists, and false otherwise.

Clarifying Questions

  1. Can c be zero?
    • Yes, c can be zero.
  2. What is the range of c?
    • Typically, c ranges from (0) to (2^{31} - 1) as it is a non-negative integer type.
  3. Do we need to consider negative values for a and b?
    • No, as per the problem statement, we are considering non-negative integers only.

Strategy

  1. Use the Two-pointer Technique:
    • Since the problem involves checking sums of squares, a common approach is using two pointers or two variables to iterate through possible values.
  2. Initialization:
    • Set a to 0 and b to the integer part of the square root of c.
  3. Loop and Check:
    • While a is less than or equal to b, calculate a^2 + b^2.
    • If the sum equals c, return true.
    • If the sum is less than c, increment a.
    • If the sum is greater than c, decrement b.

Code

#include <iostream>
#include <cmath>

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long a = 0;
        long long b = static_cast<long long>(std::sqrt(c));
        
        while (a <= b) {
            long long sum = a * a + b * b;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                ++a;
            } else {
                --b;
            }
        }
        return false;
    }
};

// Example usage:
int main() {
    Solution sol;
    int testValue = 5;
    if (sol.judgeSquareSum(testValue)) {
        std::cout << "True" << std::endl;
    } else {
        std::cout << "False" << std::endl;
    }
    return 0;
}

Time Complexity

Thus, the overall time complexity is:

[O(\sqrt{c})]

This efficient approach allows determining if there are two integers whose squares sum up to c without resorting to more computationally expensive methods.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI