Reference: LeetCode

Difficulty: Easy

## Problem

Given a non-negative integer

`c`

, your task is to decide whether there’re two integers`a`

and`b`

such that $a^2 + b^2 = c$.

**Example:**

1 | Input: 5 |

## Analysis

### Brute-Force

**Note:** Use `long`

type.

1 | public boolean judgeSquareSum(int c) { |

**Time:** $O(c^2)$**Space:** $O(1)$

**Improvement:** Up to $\sqrt{c}$.

1 | public boolean judgeSquareSum(int c) { |

**Time:** $O(c) = O(\sqrt{c} \times \sqrt{c})$**Space:** $O(1)$

### HashSet

Just like the Two Sum problem.

**Note:** Use `long`

.

1 | public boolean judgeSquareSum(int c) { |

**Time:** $O(\sqrt{c})$**Space:** $O(\sqrt{c})$

### Math

The square of $n^{th}$ positive integer can be represented as a sum of first $n$ odd positive integers.

$$n^2 = 1 + 3 + 5 + \ldots + (2 \cdot n - 1) = \sum^n_{i=1} (2\cdot i - 1)$$

1 | public boolean judgeSquareSum(int c) { |

**Time:** $O(c)$**Space:** $O(1)$

### Using Sqrt Function

1 | public boolean judgeSquareSum(int c) { |

**Time:** $O(\sqrt{c}\log{c})$. For each $a$, finding square root of $c - a^2$ takes $O(\log{c})$ time in the worst case.**Space:** $O(1)$

### Binary Search

The search range is `[0, c - a * a]`

.

1 | public boolean judgeSquareSum(int c) { |

**Time:** $O(\sqrt{c}\log{c})$**Space:** $O(1)$

### Fermat Theorem

**Fermat Theorem:** Any positive number $n$ is expressible as a sum of two squares if and only if the prime factorization of $n$, every prime of the form $(4k + 3)$ occurs an even number of times.

By making use of this theorem, we can directly find out if the given number $c$ can be expressed with a sum of two squares.