Given a integer c, your task is to decide whether there're two integers a and b such that a^2 + b^2 = c.Have you met this question in a real interview? YesProblem Correction
Example
Given n = 5
Return true // 1 * 1 + 2 * 2 = 5
Given n = -5
Return false
时间复杂度：O(c^-2* log(c))
public class Solution {
/**
* @param num: the given number
* @return: whether whether there're two integers
*/
public boolean checkSumOfSquareNumbers(int num) {
// write your code here
if(num == 0 || num == 1){
return true;
}
for (long a = 0; a* a <= num; a++ ){
//b^2 = num - a ^2;
int b = num - (int)(a*a);
if(binarySearch(b)){
return true;
}
}
return false;
}
public boolean binarySearch(int num){
if(num == 0 || num == 1)
return true;
long start = 0, end = (long)num -1;
while(start + 1 < end){
long mid = start+ (end - start)/2;
if(mid * mid < num){
start = mid;
}else{
end = mid;
}
}
if(start * start == (long)num || end*end == (long)num)
return true;
return false;
}
}
class Solution {
public boolean judgeSquareSum(int c) {
//binary search, a c - a*a binary search res, which can be
if(c == 0 || c == 1)
return true;
for(long a = 0; a*a <= c ;a++){
long b = c - a * a;
if(binarySearch(b)){
return true;
}
}
return false;
}
public boolean binarySearch(long x){
long start = 1, end = x-1;
while(start + 1 < end){
long mid = start + (end-start) /2;
if(mid * mid == x)
return true;
if(mid*mid < x){
start = mid;
}else{
end = mid;
}
}
if(start*start == x || end * end == x){
return true;
}
return false;
}
}
