633. Sum of Square Numbers

LeetCode 633. Sum of Square Numbers

Description

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

Example 1:

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

Example 2:

Input: c = 3
Output: false

Example 3:

Input: c = 4
Output: true

Constraints:

• 0 <= c <= 2^31 - 1

Tags

Math, Two Pointers

Solution

With two pointers a and b, starting from 0 and square root of c respectively, we can keep checking for the existence of a^2 + b^2 == c before they encounter.

Complexity

• Time complexity: $O(\sqrt c)$

• Space complexity: $O(1)$

Code

func judgeSquareSum(c int) bool {
	for l, r := 0, int(math.Sqrt(float64(c))); l <= r; {
		sum := l*l + r*r
		if sum == c {
			return true
		}
		if sum > c {
			r--
		} else {
			l++
		}
	}
	return false
}

Reference

1. 平方数之和