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
2
3
4
5
6
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Input: 3
Output: False

Analysis

Brute-Force

Note: Use long type.

1
2
3
4
5
6
7
8
9
10
public boolean judgeSquareSum(int c) {
  for (long i = 0; i <= c; ++i) {
    for (long j = 0; j <= c; ++j) {
      if (i * i + j * j == c) {
        return true;
      }
    }
  }
  return false;
}

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

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

1
2
3
4
5
6
7
8
9
10
public boolean judgeSquareSum(int c) {
  for (long a = 0; a * a <= c; ++i) {
    for (long b = 0; b * b <= c; ++j) {
      if (a * a + b * b == c) {
        return true;
      }
    }
  }
  return false;
}

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

HashSet

Just like the Two Sum problem.

Note: Use long.

1
2
3
4
5
6
7
8
9
10
public boolean judgeSquareSum(int c) {
  Set<Long> set = new HashSet<>();
  for (long i = 0; i * i <= c; ++i) {
    set.add(i * i);
    if (set.contains(c - i * i)) {
      return true;
    }
  }
  return false;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
public boolean judgeSquareSum(int c) {
  for (long a = 0; a * a <= c; ++a) { // ~ O(sqrt(c))
    int b = c - (int) (a * a);
    int i = 1, sum = 0;
    while (sum < b) { // ~ O(sqrt(c)/2)
      sum += i, i += 2;
    }
    if (sum == b) {
      return true;
    }
  }
  return false;
}

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

Using Sqrt Function

1
2
3
4
5
6
7
8
9
public boolean judgeSquareSum(int c) {
  for (long a = 0; a * a <= c; ++a) { // sqrt(c)
    double b = Math.sqrt(c - a * a);
    if (b == (int) b) {
      return true;
    }
  }
  return false;
}

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].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean judgeSquareSum(int c) {
  for (long a = 0; a * a <= c; ++a) {
    long val = c - a * a;
    // binary search: [0, c - a*a]
    long lo = 0, hi = val;
    while (lo <= hi) {
      long mid = lo + (hi - lo) / 2;
      if (mid * mid >= val) { // mid could be 0
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    // check
    if (lo * lo == val) {
      return true;
    }
  }
  return false;
}

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