Code Implementation

import math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left = 0
        right = int(math.isqrt(c))
        while left <= right:
            curr = left * left + right * right
            if curr == c:
                return True
            elif curr < c:
                left += 1
            else:
                right -= 1
        return False
      

class Solution {
public:
    bool judgeSquareSum(int c) {
        long left = 0;
        long right = (long)sqrt(c);
        while (left <= right) {
            long curr = left * left + right * right;
            if (curr == c) return true;
            else if (curr < c) left++;
            else right--;
        }
        return false;
    }
};
      

class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long)Math.sqrt(c);
        while (left <= right) {
            long curr = left * left + right * right;
            if (curr == c) return true;
            else if (curr < c) left++;
            else right--;
        }
        return false;
    }
}
      

var judgeSquareSum = function(c) {
    let left = 0;
    let right = Math.floor(Math.sqrt(c));
    while (left <= right) {
        let curr = left * left + right * right;
        if (curr === c) return true;
        else if (curr < c) left++;
        else right--;
    }
    return false;
};
      

Problem Description

Given a non-negative integer c, determine whether it can be expressed as the sum of the squares of two integers. In other words, does there exist two integers a and b such that:

a * a + b * b = c

You can use the same number for both a and b. The solution should return true if such a pair exists, and false otherwise.

• Input: a single integer c (0 ≤ c ≤ 2³¹ - 1)
• Output: true if there exist integers a and b such that a² + b² = c, else false
• Each pair (a, b) is valid if both are integers and their squares sum to c

Thought Process

The most direct way to solve this problem is to try every possible pair of numbers a and b such that a * a + b * b = c. However, this brute-force approach would require checking all pairs up to sqrt(c), which can be slow for large c.

Instead, we can optimize by recognizing that for each possible a (from 0 to sqrt(c)), the value c - a*a must also be a perfect square if a solution exists. This leads to a more efficient approach: for each a, check if c - a*a is a perfect square.

An even more efficient method uses the two-pointer technique, starting with left = 0 and right = sqrt(c), and adjusting the pointers based on the sum of their squares. This reduces unnecessary checks and leverages the sorted nature of squares.

Solution Approach

• Step 1: Initialize two pointers:
  • left starts at 0
  • right starts at sqrt(c)
• Step 2: While left is less than or equal to right:
  • Compute curr = left * left + right * right
  • If curr == c, return true (found a solution)
  • If curr < c, increment left (need a larger sum)
  • If curr > c, decrement right (need a smaller sum)
• Step 3: If the loop ends without finding a solution, return false.

This approach works because the sum left*left + right*right increases as left increases and decreases as right decreases, allowing us to efficiently explore all possible pairs without redundant checks.

Example Walkthrough

Let's use c = 5 as an example.

• Initialize: left = 0, right = 2 (since sqrt(5) ≈ 2.23)
• First iteration:
  • curr = 0*0 + 2*2 = 0 + 4 = 4
  • 4 < 5, so increment left to 1
• Second iteration:
  • curr = 1*1 + 2*2 = 1 + 4 = 5
  • 5 == 5, so we return true

The process finds that 5 can be expressed as 1^2 + 2^2.

Time and Space Complexity

• Brute-force approach:
  • Time complexity: O(c), since we might check all pairs up to sqrt(c) for both a and b.
  • Space complexity: O(1), as we only use a few variables.
• Optimized (two-pointer) approach:
  • Time complexity: O(sqrt(c)), since each iteration moves either left or right closer together, with at most sqrt(c) steps.
  • Space complexity: O(1), as only two pointers and a few variables are used.

Summary

The "Sum of Square Numbers" problem asks whether a number can be written as the sum of two squares. By leveraging the two-pointer technique and the properties of squares, we can efficiently check all possible pairs in O(sqrt(c)) time. This approach avoids redundant calculations and demonstrates how mathematical insight can lead to elegant and performant code.