Solution to Leetcode’s Valid Perfect Square

This is an easy Leetcode problem 367. The question gives a number and you are to write a function to determine if it is a perfect square. See the image below for description.

Valid perfect square description. Leetcode 367

According to wikipedia, a perfect square is the product of a number with itself. in this context, a perfect square is a number when multiplied by itself will give you the number in question.

There are many ways in solving this problem but I will talk about three in this article.

NOTE: Do not use any library functions like Math.sqrt().

THE NAIVE APPROACH

Of course the naive or brute force approach would be to loop through from 1 to the number, multiplying a number by itself and checking if the product equals the number you are looking for. if it does, then return true, else return false.

public static boolean isPerfectSquareWithBruteForce(int num) {
    if (num == 1) return true;
    for (int i = 1; i < num; i++) {
        if (i*i == num) return true;
    }
    return false;
}

The code above works but can be very slow. its runtime is O(n).

To make this better, we may decide to loop from 1 to half of the number because there is no way you can get the number in question by multiplying number greater than half (i.e num/2) by itself. e.g to determine if 9 is a perfect square, there is no way a number between 4 to 9 would give you 9. So in other words, to know if a number is a perfect square, the number that will multiply itself will have to be in the first half (between 1–3).

public static boolean isPerfectSquareWithHalfNumber(int num) {
    if (num ==  1 || num ==  0) return true;
    for (int i = 1; i < num/2; i++ ) {
        if (i*i == num) return true;
    }

    return false;
}

Technically speaking, it may seem that the above code would make it faster but the truth is , the runtime of this is O(n/2) which still translates to O(n) because in computer science, we don’t consider constants when dealing with runtime.

A FASTER SOLUTION

A better way to solve this problem would be to use Binary Search. This solves the problem by using the divide and conquer methodology. It keeps splitting the number into half and checking if number is found.

public static boolean isPerfectSquareWithBinarySearch(int num) {

    double start = 1;
    double end = num/2;

    if (num == 1) return true;

    while (start <= end) {
        double mid = Math.floor((end - start)/2) + start;

        if (mid * mid ==  num) {
            return true;
        }else if (mid * mid < num) {
            start = mid + 1;
        }else {
            end = mid - 1;
        }
    }
    return false;
}

The runtime of the above is O(log n) which is faster than O(n) linear time.

Thank you for reading and please leave a comment.