Welcome to Subscribe On Youtube

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

The picture above shows the relationship between a, b, and c. This question is actually looking up c in this table

From the upper right corner of the table, it is not difficult to find that it is similar to a binary search tree, so just start from the upper right corner and search according to the law of the binary search tree

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

  • 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;
    }
}


// Solution 2
class Solution {
    public boolean judgeSquareSum(int c) {
        int n = (int) Math.sqrt(c);
        for (int i = 2; i <= n; ++i) {
            if (c % i == 0) {
                int exp = 0;
                while (c % i == 0) {
                    c /= i;
                    ++exp;
                }
                if (i % 4 == 3 && exp % 2 != 0) {
                    return false;
                }
            }
        }
        return c % 4 != 3;
    }
}


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


// Solution 2
class Solution {
public:
    bool judgeSquareSum(int c) {
        int n = sqrt(c);
        for (int i = 2; i <= n; ++i) {
            if (c % i == 0) {
                int exp = 0;
                while (c % i == 0) {
                    c /= i;
                    ++exp;
                }
                if (i % 4 == 3 && exp % 2 != 0) {
                    return false;
                }
            }
        }
        return c % 4 != 3;
    }
};


  • 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


# Solution 2
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        for i in range(2, int(sqrt(c)) + 1):
            if c % i == 0:
                exp = 0
                while c % i == 0:
                    c //= i
                    exp += 1
                if i % 4 == 3 and exp % 2 != 0:
                    return False
        return c % 4 != 3


  • 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
}


// Solution 2
func judgeSquareSum(c int) bool {
	n := int(math.Sqrt(float64(c)))
	for i := 2; i <= n; i++ {
		if c%i == 0 {
			exp := 0
			for c%i == 0 {
				c /= i
				exp++
			}
			if i%4 == 3 && exp%2 != 0 {
				return false
			}
		}
	}
	return c%4 != 3
}


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


// Solution 2
function judgeSquareSum(c: number): boolean {
    const n = Math.floor(Math.sqrt(c));
    for (let i = 2; i <= n; ++i) {
        if (c % i === 0) {
            let exp = 0;
            while (c % i === 0) {
                c /= i;
                ++exp;
            }
            if (i % 4 === 3 && exp % 2 !== 0) {
                return false;
            }
        }
    }
    return c % 4 !== 3;
}


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

All Problems

All Solutions