LC633 - Sum of Square Numbers

Problem

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

Example

Input: c = 5

Output: true

Explanation: 1 * 1 + 2 * 2 = 5

Solution

Use Fermat's theorem for $O(\sqrt(n))$ Time Complexity.

Basic

def judgeSquareSum(self, c: int) -> bool:
	# iterate from a 
	for a in range(int(math.sqrt(c))+1):
		b = math.sqer(c - pow(a,2))
		if b % 1 == 0:
			return True
	return False

Faster

def judgeSquareSum(self, c: int) -> bool:
	div = 2
	while pow(div, 2) <= c:
		if c % div == 0:
			exp = 0
			while c % div == 0:
				exp += 1
				c //= div
			if div % 4 == 3 and exp % 2 != 0:
				return False
		div += 1
	return c % 4 != 3