How to find if a number is perfect square

Number problems are abound in the programming interview world. A perfect square (also called a square number) is an integer that is the square of an integer; in other words, it is the product of some integer with itself. So, for example, 9 is a square number, since it can be written as 3 × 3. So are 16, 25, 49 and so on.

So how do we find if a given number is a square number or not? There are a many ways. This is a big research topic in the mathematics world. For the purpose of interview, we will not delve into highly complex solutions.

A bad implementation would be something like this:

public static bool IsSquare(long target)
{
    // loop through all the numbers till the target
    for (long i = 0; i < target; i++)
    {
        // if we have a match
        if ((i * i) == target)
        {
            return true;
        }
    }

    // no matching number could be squared
    return false;
}

This is an inefficient solution. There is no need to loop till the element. The only case when this would be true is 1. Beyond that, if a number is a square, it’s square root has to be less than half of the number (4 – 2, 9 – 3, 16 – 4, 25 – 5 an so on. Let’s modify our algorithm to add this logic.

Still a bad implementation:

public static bool IsSquare(long target)
{
    // loop through HALF the numbers till the target
    for (long i = 0; i < target/2; i++)
    {
        // if we have a match
        if ((i * i) == target)
        {
            return true;
        }
    }

    // no matching number could be squared
    return false;
}

Even though we have cut our loop by half, this is still inefficient. So what can we do more to stop the loop earlier. Let’s assume that our target number was 20. So using the code above, we will be looping till 10. Now once the loop crosses 5, we know that none of the numbers above that will result in the loop being true. So, a good condition to add would be break if the square of the current number is greater than the target. Let’s review this code below:

public static bool IsSquare(long target)
{
    // handle 0 and 1
    if (target <= 1)
        return true;

    long currentSquare = 4;
    long currentNumber = 2;

    // loop through till the target is more than
    // the square of the current number
    while (currentSquare <= target)
    {
        // if we have a match, return true
        if (currentSquare == target)
            return true;
        // increment current number
        currentNumber++;
        // find the next square
        currentSquare = currentNumber * currentNumber;
    }

    // no matching number could be squared
    return false;
}

Yes, this is still not the best solution but these code snippets should give you a good enough idea on how to optimize this algorithm further. I challenge the readers to take a few minutes out and come up with a better solution.