# 633. Sum of Square Numbers

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:

## Analysis

### Brute-Force

Note: Use long type.

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

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

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

### HashSet

Just like the Two Sum problem.

Note: Use long.

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)$$

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

### Using Sqrt Function

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)$

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

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.

More Details

Comment
Junhao Wang
a software engineering cat