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 there are such integers a and b, otherwise return false.

Clarifying Questions

  1. Input Constraints:
    • Is c guaranteed to be a non-negative integer?
    • Is there a maximum value for c?

    Answer:

    • Yes, c is guaranteed to be a non-negative integer.
    • In general Leetcode problems, the value for c usually fits within the range of a typical 32-bit signed integer.
  2. Output:
    • The function should return a boolean true or false.

Strategy

The problem can be approached using the two-pointer technique. Here’s the plan:

  1. Initialize Two Pointers:
    • One pointer (a) starts at 0.
    • Another pointer (b) starts at the integer square root of c (i.e., the largest b such that b^2 <= c).
  2. Two Pointer Algorithm:
    • Compute the sum of squares of the current a and b pointers.
    • If the sum equals c, return true.
    • If the sum is less than c, increment a to increase the sum.
    • If the sum is greater than c, decrement b to decrease the sum.
    • Continue this process until a surpasses b.
  3. Exit Condition:
    • If a surpasses b, return false, because no such pair (a, b) was found.

Code

public class Solution {
    public boolean judgeSquareSum(int c) {
        int a = 0;
        int b = (int) Math.sqrt(c);
        
        while (a <= b) {
            int sum = a * a + b * b;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                a++;
            } else {
                b--;
            }
        }
        
        return false;
    }
}

Time Complexity

Therefore, the overall time complexity is (O(\sqrt{c})), since the time complexity to find the square root is minimal compared to the two-pointer traversal. The space complexity is (O(1)) as we are using a constant amount of space.

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