Please navigate to the bottom of the page for Table of Contents

Saturday, May 28, 2011

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.

24 comments:

  1. Im a kid. How would you explain it to me?

    ReplyDelete
    Replies
    1. boova saappudu chellam.....:)

      Delete
  2. Add a check if the number does not end with 0,1,4,5,9 return false;

    ReplyDelete
    Replies
    1. then 16 isnt a square. Idiot. :|

      Delete
  3. You guys are trying way to hard.

    public static bool IsSquare(long target)
    {
    return Math.Sqrt((double)target) % 1d == 0d;
    }

    ReplyDelete
    Replies
    1. yes it is good.But without using built in functions..
      we need top go in other way that i Need .Thanks in advance

      Delete
    2. @Jacob
      The point is in programming interviews you'll be asked not to used libraries. Otherwise, if the interviewer asks you to write a function for binary search, you could write:
      return System.Array.BinarySearch(...);
      Hahaha!

      Delete
  4. This comment has been removed by the author.

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Dear Nikhil Singhal,

    Is he following a better solution in terms of efficiency??
    Thank you.

    int x;
    bool flag=false;
    cin>>x;
    for (int i=2;i < x/2;i++)
    {
    if(x%i==0)
    {
    if (i*i==x)
    {
    flag=true;
    break;
    }
    }

    }

    if(flag) cout<<"Perfect square";
    else cout<>x;

    ReplyDelete
  7. You could do a binary search instead. Start with i = median(n). Then compare i^2 with n to determine which direction to go. Repeat until you have an i value such that i^2 == n or until you've exhausted all viable possibilities. Run-time is O(lg n) assuming multiplication is a constant-time operation.

    ReplyDelete
  8. this is not bad:
    private static bool IsSquare(long value)
    {
    double temp = Math.Sqrt(value);
    return unchecked(temp == (int)temp);
    }

    ReplyDelete
    Replies
    1. sir, May i know how exact compare does between temp and int(temp), what double temp variable will stores.?

      Delete
  9. what about (x & (x-1)) == 0 ?

    ReplyDelete
    Replies
    1. this is for checking if no. is a power of 2 or not

      Delete
  10. bool isPerfectSquare(long input)
    {
    // return true for trivial cases
    if( input == 0 || input == 1)
    {
    return true;
    }
    else if( input == -1)
    {
    return false;
    }

    // make an initial guess and store as a floating point.
    // the divisor is arbitrary, testing would have to be done to choose an optimal value
    // basically the closer the initial value the faster the solution
    double guess = input /2.0;

    // uses approximation equation for 20 iterations or until the guess is close enough
    // the max number of iterations could be adjusted
    for(int i = 0; i < 20; i++)
    {
    // if the guess, is correct it will exit the loop.
    if( guess * guess == input)
    {
    return true;
    }

    guess = 1.0/2.0 *( guess + input/guess);
    }
    return false;
    }

    ReplyDelete
  11. public static boolean isSquare(int n)
    {
    int k=1;
    while (n!=0)
    {
    if (n<0)
    return false;

    else
    {
    n=n-k;
    k+=2;
    }
    }
    return true;
    }

    ReplyDelete
  12. This could be solved in a constant time O(C), given that integers have fixed bit-size. Digit-by-digit algorithm will have O(M) complexity, where M is number of bits in integer. Still the implementation is somewhat complicated.

    ReplyDelete
  13. public static bool isPerfectSquare(long target)
    {
    long result,perfSquare = target / 2;
    do{
    result = perfSquare * perfSquare;
    if (result == target)
    return true;
    else if (target < result)
    perfSquare = perfSquare - 1;
    else
    perfSquare = perfSquare / 2;
    }while(target<result);
    return false;
    }

    ReplyDelete
    Replies
    1. your looping as normal from half
      Example : for 25 , your looping from 12,11,10.....5 (7 times)
      programming should change to

      public static bool isPerfectSquare(long target)
      {
      long result,perfSquare = target / 2;
      do{
      result = perfSquare * perfSquare;
      if (result == target)
      return true;
      else if (result > target)
      perfSquare = perfSquare / 2;
      else
      {
      perfSquare = perfSquare * 2 - 1;
      result = perfSquare * perfSquare;
      if (result == target)
      return true;
      }
      }while(target<result);
      return false;
      }

      This allows to loop around values for 25 (12,6,3 then 5 result) 3 times..

      Delete
  14. One can keep adding odd integers starting from 1, until the sum matches the number (ansewer=yes) or exceedes (answer=no).
    1 = 1^2
    1+3 = 2^2
    1+3+5 = 3^2
    ....
    This is still a linear solution but addition is cheaper than multiplication.

    ReplyDelete
  15. public static bool IsSquare(int target)
    {
    for (int i = 0; i <= Math.Sqrt(target); i++)
    {
    System.Console.WriteLine(Math.Sqrt(target));
    if (i * i == target)
    {
    return true;

    }

    }
    return false;

    }

    better?

    ReplyDelete