633. Sum of Square Numbers

Problem

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

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

Problem Summary

Given a non-negative integer c, you need to determine whether there exist two integers a and b such that a^2 + b^2 = c.

Solution Approach

• Given a number, determine whether it can be composed of 2 perfect squares. If it can, output true; otherwise, output false.
• This problem can be solved using binary search. According to the problem statement, compute low * low + high * high in sequence and check whether it equals c. Perform binary search within the interval [0, sqrt(n)]; if it can be found, return true; otherwise, return false.

Code

package leetcode

import "math"

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