Valid Perfect Square

In the problem statement, it is mentioned that we cannot use any inbuilt functions such as Math.sqrt(num). So one possible solution we could implement is, check square of each number starting from 1 and check whether it matches input num, if it matches we can return true, otherwise continue until we find the square of a number that matched input number and when we go beyond input number and cant find a perfect square then return false, and the time complexity of this approach is going to be O(√n).

We can solve this problem using binary search, which runs in O(log n) time complexity. So, in this approach, we will initialize two variables left =1 and right = num that acts as left and right boundaries. Then using a while loop, compute the middle index mid = $\left[\begin{array}{c}\mathrm{left\; +\; right}\\ \mathrm{\_\_\_\_\_\_\_\_\_\_\_\_\_}\\ 2\end{array}\right]$ , then compute the square of the mid value, based on square value we can draw three conclusions.

• If square value is equal to num, then return true since the square computed using mid is a perfect integer.
• If square value is greater than num, this means that the target lies on left side, so we will update right value to mid-1.
• If square value is less than num, this means that the target lies on right side, so we will update left value to mid+1.

If that num is not found, we will return false at the end.

public class ValidPerfectSquare {

    static boolean isPerfectSquare(int num) {
        int left = 1;
        int right = num;
        while(left <= right) {
            int mid = left + (right - left) /2;
            long sqrt = (long)mid * mid;
            if (sqrt == num) {
                return true;
            } else if (sqrt > num) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isPerfectSquare(16));
        System.out.println(isPerfectSquare(14));
        System.out.println(isPerfectSquare(2147483647));
    }
}

Complexity Analysis:

Time complexity: Above code runs in O(log n) time where n is the length of input number num.
Space complexity: O(1).