[LeetCode] 633. Sum of Square Numbers

轉自LeetCode

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

Example 1:

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

Example 2:

Input: 3
Output: False

<Solution>

想法如下

• a 和 b 一定會小於等於 c 的平方根，不然相加一定會超過 c

• 當 c - a 的時候，如果 b 存在，那麼 b 一定是 c-a 的平方根

code 如下

C++

	class Solution {
	public:
	bool judgeSquareSum(int c) {
	const int upperBound = static_cast<int>(sqrt(c));
	double val;
	for(int i = 0; i <= upperBound; ++i) {
	val = sqrt(c - i * i);
	if(val - floor(val) == 0) {
	return true;
	}
	}
	return false;
	}
	};

view raw sumOfSquareNumber.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public boolean judgeSquareSum(int c) {
	final int upperBound = (int)Math.sqrt(c);
	double val;
	for(int i = 0; i <= upperBound; i++) {
	val = Math.sqrt(c - i*i);
	if(val - Math.floor(val) == 0) {
	return true;
	}
	}
	return false;
	}
	}

view raw sumOfSquareNumber.java hosted with ❤ by GitHub