Accepted Java O(m log m) : m = sqrt of num


  • 0
    M
    public boolean judgeSquareSum(int c) {
            double sqrt = Math.sqrt(c);
    	int x = (int) sqrt;
    
    	// Check if given number is a perfect square
    	if (Math.pow(sqrt, 2) == Math.pow(x, 2)) {
    		return true;
    	}
    
    	int limit = (int) Math.sqrt(c);
    	int[] squares = new int[limit];
    
    	// Calculate squares of all the numbers until squareroot digit
    	for (int i = 0; i < limit; i++) {
    		squares[i] = (i + 1) * (i + 1);
    	}
    
    	for (int i = limit - 1; i >= 0; i--) {
    		int target = c - squares[i];
    	        // Scan and compare if remainder exists in squares array
    		int pos = Arrays.binarySearch(squares, 0, i + 1, target);
    		if (pos >= 0) {
    			return true;
    		}
    	}
    	return false;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.