# Sum of Square Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-square-numbers)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-square-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Two Sigma](https://scaleengineer.com/companies/two-sigma)
---
## Problem
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`

# Approaches
## Brute Force with Nested Loops
This is the most straightforward, brute-force approach. We can check every possible pair of integers `(a, b)` to see if their squares sum up to `c`. Since `a^2` and `b^2` must be less than or equal to `c`, the values of `a` and `b` must be in the range from `0` to `sqrt(c)`.
**Time:** O(c). The two nested loops each run up to `sqrt(c)` times, leading to `sqrt(c) * sqrt(c) = c` iterations in the worst case. · **Space:** O(1), as we only use a few variables to store the loop counters.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient for large values of `c`.; Will likely result in a 'Time Limit Exceeded' error on most online judges.
### Explanation
We use two nested loops to explore all combinations of `a` and `b`. The outer loop iterates `a` from `0` to `sqrt(c)`, and the inner loop iterates `b` from `0` to `sqrt(c)`. Inside the inner loop, we calculate `a^2 + b^2` and check if it equals `c`. If it does, we've found a solution and can return `true` immediately. If the loops complete without finding such a pair, it means no solution exists, and we return `false`. To avoid potential integer overflow when calculating `a*a + b*b` for large `c`, it's safer to use a `long` data type for the loop variables and the sum.

```java
class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            for (long b = 0; b * b <= c; b++) {
                if (a * a + b * b == c) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- Iterate a variable `a` from `0` up to `sqrt(c)`.
- Inside this loop, iterate another variable `b` from `0` up to `sqrt(c)`.
- In the inner loop, calculate the sum `a*a + b*b`.
- If the sum equals `c`, a valid pair `(a, b)` has been found, so return `true`.
- If the loops complete without finding any such pair, it means no solution exists. Return `false`.

## Optimized Brute Force with Square Root
We can significantly optimize the brute-force approach by eliminating the inner loop. Instead of iterating through all possible values of `b`, we can iterate only through `a` and then directly calculate the required value of `b`.
**Time:** O(sqrt(c) * log(c)). The loop runs `sqrt(c)` times. Inside the loop, `Math.sqrt` is called, which typically has a time complexity of O(log c). · **Space:** O(1), as only a few variables are needed.
**Pros:** Much faster than the nested loop approach.; Still relatively simple to understand.
**Cons:** Relies on floating-point arithmetic, which can have precision issues, though it's generally safe for this problem.; The `Math.sqrt` function call inside the loop can be less performant than pure integer arithmetic.
### Explanation
The governing equation is `a^2 + b^2 = c`. We can rearrange it to solve for `b`: `b^2 = c - a^2`, which implies `b = sqrt(c - a^2)`. This insight allows us to use a single loop. We iterate `a` from `0` to `sqrt(c)`. In each iteration, we calculate the value that `b^2` would need to be: `c - a*a`. Then, we take the square root of this result to find `b`. If this `b` is a whole number, we have found a valid pair `(a, b)` and can return `true`. We can check if `b` is an integer by comparing it with its truncated version `(int)b`.

```java
class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Iterate `a` from `0` up to `sqrt(c)`.
- For each `a`, calculate the required value for `b^2`, which is `b_squared = c - a*a`.
- Calculate `b = sqrt(b_squared)`.
- Check if `b` is an integer. A simple way is to check if `b` is equal to its integer cast, i.e., `b == (int)b`.
- If `b` is an integer, it means we have found a valid pair, so return `true`.
- If the loop finishes without finding such an `a`, return `false`.

## Two Pointers Approach
This efficient approach treats the problem as a search on a sorted range. We search for two numbers, `a` and `b`, in the conceptual range of `[0, sqrt(c)]`. By using two pointers starting from the ends of this range, we can cleverly narrow down the search space.
**Time:** O(sqrt(c)). The `left` pointer moves from `0` upwards, and the `right` pointer moves from `sqrt(c)` downwards. The pointers will cross in at most `sqrt(c)` steps. · **Space:** O(1). We only use a few variables for the pointers and the sum.
**Pros:** Highly efficient with a linear scan over the search space.; Easy to implement and avoids complex math functions or floating-point arithmetic inside the loop.; Generally one of the fastest solutions in practice.
**Cons:** While efficient, it might be slightly less intuitive than a direct brute-force search for beginners.
### Explanation
We initialize two pointers: a `left` pointer starting at `0` and a `right` pointer starting at `(int)sqrt(c)`. These represent our candidate values for `a` and `b`. We then loop as long as `left <= right`.
In each iteration, we compute the sum of squares `sum = left*left + right*right`.
- If `sum` equals `c`, we've found our pair, and we can return `true`.
- If `sum` is less than `c`, it means our sum is too small. To get a larger sum, we need to increase one of our numbers. Since `right` is already large, we increase the smaller number by incrementing the `left` pointer.
- If `sum` is greater than `c`, our sum is too large. To reduce it, we decrease the larger number by decrementing the `right` pointer.
This process continues until the pointers meet or cross. If the loop finishes, no pair was found, and we return `false`.

```java
class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize two pointers: `left = 0` and `right = (long)Math.sqrt(c)`.
- Loop as long as `left <= right`.
- Calculate the current sum of squares: `sum = left*left + right*right`.
- If `sum == c`, a solution is found, return `true`.
- If `sum < c`, the sum is too small. To increase it, increment the `left` pointer: `left++`.
- If `sum > c`, the sum is too large. To decrease it, decrement the `right` pointer: `right--`.
- If the loop completes without finding a solution, return `false`.

## Number Theory: Fermat's Theorem
This approach leverages a deep result from number theory, specifically Fermat's theorem on sums of two squares. This theorem provides a direct criterion for determining if a number can be written as the sum of two squares based on its prime factorization.
**Time:** O(sqrt(c)). The trial division for prime factorization runs up to `sqrt(c)` in the worst case (e.g., when `c` is a large prime). · **Space:** O(1). Constant extra space is used.
**Pros:** Provides an elegant mathematical solution.; Can be very fast if `c` is composed of small prime factors.
**Cons:** Relies on non-trivial number theory (Fermat's theorem), making it less intuitive.; The logic involving prime factorization is more complex to implement correctly than the two-pointer approach.
### Explanation
The theorem states that a non-negative integer `n` can be expressed as a sum of two squares if and only if every prime factor of `n` of the form `4k + 3` appears with an even exponent in its prime factorization.

To apply this, we need to find the prime factors of `c` and their exponents. We can do this using trial division. We iterate from `i = 2` up to `sqrt(c)`. If we find a divisor `i`, we know it's a prime factor. We then count how many times it divides `c` to find its exponent. If this prime factor `i` gives a remainder of 3 when divided by 4, and its exponent is odd, we can conclude from the theorem that `c` cannot be a sum of two squares and return `false`. After checking all factors up to `sqrt(c)`, if the remaining `c` is greater than 1, it is itself a prime factor with an exponent of 1. We must perform the same check on this final factor. If all prime factors of the form `4k+3` have even exponents, we return `true`.

```java
class Solution {
    public boolean judgeSquareSum(int c) {
        for (int i = 2; i * i <= c; i++) {
            if (c % i == 0) {
                int count = 0;
                while (c % i == 0) {
                    count++;
                    c /= i;
                }
                if (i % 4 == 3 && count % 2 != 0) {
                    return false;
                }
            }
        }
        // After the loop, if c > 1, the remaining c is a prime factor with exponent 1.
        return c % 4 != 3;
    }
}
```
### Algorithm
- Iterate through potential prime factors `i` from 2 up to `sqrt(c)`.
- If `i` divides `c`:
  - Count its exponent: while `c` is divisible by `i`, increment a counter and divide `c` by `i`.
  - Check if the prime `i` is of the form `4k + 3` (i.e., `i % 4 == 3`).
  - If it is, and its exponent is odd, return `false` immediately.
- After the loop, the remaining value of `c` (if greater than 1) is also a prime factor with an exponent of 1.
- Check if this final factor `c` is of the form `4k + 3`. If so, return `false`.
- If all prime factors satisfy the condition, return `true`.

# Solutions
### Java

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

### CPP

```cpp
class Solution { public: bool judgeSquareSum ( int c ) { long a = 0 , b = ( long ) sqrt ( c ); while ( a <= b ) { long s = a * a + b * b ; if ( s == c ) return true ; if ( s < c ) ++ a ; else -- b ; } return false ; } };
```

### Python

```python
class Solution : def judgeSquareSum ( self , c : int ) -> bool : a , b = 0 , int ( sqrt ( c )) while a <= b : s = a ** 2 + b ** 2 if s == c : return True if s < c : a += 1 else : b -= 1 return False
```