Sum of Square Numbers

lintcode 的答案在leetcode跑不过，a和b应该都用long

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;
    }
}