633. Sum of Square Numbers
Description
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
Solutions
Solution 1: Mathematics + Two Pointers
We can use the two-pointer method to solve this problem. Define two pointers $a$ and $b$, pointing to $0$ and $\sqrt{c}$ respectively. In each step, we calculate the value of $s = a^2 + b^2$, and then compare the size of $s$ and $c$. If $s = c$, we have found two integers $a$ and $b$ such that $a^2 + b^2 = c$. If $s < c$, we increase the value of $a$ by $1$. If $s > c$, we decrease the value of $b$ by $1$. We continue this process until we find the answer, or the value of $a$ is greater than the value of $b$, and return false
.
The time complexity is $O(\sqrt{c})$, where $c$ is the given non-negative integer. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
Solution 2: Mathematics
This problem is essentially about the conditions under which a number can be expressed as the sum of two squares. This theorem dates back to Fermat and Euler and is a classic result in number theory.
Specifically, the theorem can be stated as follows:
A positive integer $n$ can be expressed as the sum of two squares if and only if all prime factors of $n$ of the form $4k + 3$ have even powers.
This means that if we decompose $n$ into the product of its prime factors, $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, where $p_i$ are primes and $e_i$ are their corresponding exponents, then $n$ can be expressed as the sum of two squares if and only if all prime factors $p_i$ of the form $4k + 3$ have even exponents $e_i$.
More formally, if $p_i$ is a prime of the form $4k + 3$, then for each such $p_i$, $e_i$ must be even.
For example:
- The number $13$ is a prime and $13 \equiv 1 \pmod{4}$, so it can be expressed as the sum of two squares, i.e., $13 = 2^2 + 3^2$.
- The number $21$ can be decomposed into $3 \times 7$, where both $3$ and $7$ are prime factors of the form $4k + 3$ and their exponents are $1$ (odd), so $21$ cannot be expressed as the sum of two squares.
In summary, this theorem is very important in number theory for determining whether a number can be expressed as the sum of two squares.
The time complexity is $O(\sqrt{c})$, where $c$ is the given non-negative integer. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|