JAVA O(sqrt(n)) and small tips to make the code faster


  • 0
    Z

    2 pointer solution.
    How to make the code faster?
    Let us define the pointer starts from 0 is the left and the other one is the right pointer which begins from sqrt(n)
    As the left <= right, there will have more left++ than right-- if the sum mismatch the target because the left * left increase more slower than the right * right decreasing in every ++/-- operation.
    So if there is a lot of input, the (l * l + r * r < c) check will more than the (l * l + r * r > c)
    check. and put the (l * l + r * r < c) check firstly may reduce the time cost in checking in this problem.

    class Solution {
        public boolean judgeSquareSum(int c) {
            int l = 0;
            int r = (int) Math.sqrt(c);
            while(l <= r){
                if(l*l + r*r < c) l++;
                else if(l*l + r*r > c) r--;
                else return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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