633. Sum of Square Numbers

Description

Given a non-negative integer c, decide whether there're two integers a and b such that a² + b² = c.

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: c = 3
Output: false

Constraints:

0 <= c <= 2³¹ - 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)\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        a, b = 0, int(sqrt(c))
        while a <= b:
            s = a**2 + b**2
            if s == c:
                return True
            if s < c:
                a += 1
            else:
                b -= 1
        return False

class Solution {
    public boolean judgeSquareSum(int c) {
        long a = 0, b = (long) Math.sqrt(c);
        while (a <= b) {
            long s = a * a + b * b;
            if (s == c) {
                return true;
            }
            if (s < c) {
                ++a;
            } else {
                --b;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long a = 0, b = sqrt(c);
        while (a <= b) {
            long long s = a * a + b * b;
            if (s == c) {
                return true;
            }
            if (s < c) {
                ++a;
            } else {
                --b;
            }
        }
        return false;
    }
};

func judgeSquareSum(c int) bool {
    a, b := 0, int(math.Sqrt(float64(c)))
    for a <= b {
        s := a*a + b*b
        if s == c {
            return true
        }
        if s < c {
            a++
        } else {
            b--
        }
    }
    return false
}

function judgeSquareSum(c: number): boolean {
    let [a, b] = [0, Math.floor(Math.sqrt(c))];
    while (a <= b) {
        const s = a * a + b * b;
        if (s === c) {
            return true;
        }
        if (s < c) {
            ++a;
        } else {
            --b;
        }
    }
    return false;
}

use std::cmp::Ordering;

impl Solution {
    pub fn judge_square_sum(c: i32) -> bool {
        let mut a: i64 = 0;
        let mut b: i64 = (c as f64).sqrt() as i64;
        while a <= b {
            let s = a * a + b * b;
            match s.cmp(&(c as i64)) {
                Ordering::Equal => {
                    return true;
                }
                Ordering::Less => {
                    a += 1;
                }
                Ordering::Greater => {
                    b -= 1;
                }
            }
        }
        false
    }
}

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.