# 633 Sum of Square Numbers

## 633. [Sum of Square Numbers](https://leetcode.com/problems/sum-of-square-numbers/description/)

## 1. Question

Given a non-negative integer`c`, your task is to decide whether there're two integers`a`and`b`such that a2+ b2= c.

**Example 1:**

```
Input: 5

Output: True

Explanation: 1 * 1 + 2 * 2 = 5
```

**Example 2:**

```
Input: 3

Output: False
```

## 2. Implementation

**(1) Binary Search**

```java
class Solution {
    public boolean judgeSquareSum(int c) {
        for (long num = 0; num <= (long)Math.sqrt(c); num++) {
            long target = c - num * num;

            if (isSquareNum(0, target, target)) {
                return true;
            }
        }
        return false;
    }

    public boolean isSquareNum(long start, long end, long target) {
        long mid = 0;

        while (start <= end) {
            mid = start + (end - start)/2;

            if (mid * mid == target) {
                return true;
            }
            else if (mid * mid < target) {
                start = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }
        return false;
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度Sqrt(n) \* log(Sqrt(n)), n为输入的数字，空间复杂度O(1)