16

Possible Duplicate:
Fastest way to determine if an integer's square root is an integer

Does Anybody Knows the Logic To Find Out a Number is Perfect Square or not ? (Other than Newtons Method or Synthetic Division Method)

For Eg:- 4, 16, 36, 64 are Perfect Squares.

I will be giving the input as 441, logic should say whether its a Perfect Square or not.

It was a question asked in Amazon Interview.

I would like to do it with out any built in functions

Community
  • 1
  • 1
Developer
  • 8,390
  • 41
  • 129
  • 238
  • 5
    [What's a good algorithm to determine if an input is a perfect square?](http://stackoverflow.com/questions/343852/whats-a-good-algorithm-to-determine-if-an-input-is-a-perfect-square) – Paolo Moretti Jun 30 '11 at 12:40
  • 1
    If the trick were on the input itself then, Because of 441 has one in the right then no way it could be a Perfect Squares. – Jalal Said Jun 30 '11 at 12:40
  • @Jalal: What, like 81 isn't? :-) – regularfry Jun 30 '11 at 12:51
  • @Jalal - 441 = 21^2. At least check... Besides, take any number that ends with 1, eg, 52941, multiply it by itself, and you get a square that ends with 1. – Kobi Jun 30 '11 at 12:52
  • @regularfry: @Kobi: I thought that was just for 2 to the power n. – Jalal Said Jun 30 '11 at 12:54

3 Answers3

20

No Math.Sqrt, not even multiplication:

    static bool IsSquare(int n)
    {
        int i = 1;
        for (; ; )
        {
            if (n < 0)
                return false;
            if (n == 0)
                return true;
            n -= i;
            i += 2;
        }
    }

Note that the squares are the partial sums of the odd integers. i takes on the values 1, 3, 5, 7, .... The partial sums 1, 1+3=4, 1+3+5=9, ... are the squares. So after n -= i we have subtracted the squares from the original value of n and we can compare the result against 0.

Henrik
  • 23,186
  • 6
  • 42
  • 92
3

The first question I would ask the interviewer is, "What are the problem constraints?" That is, how big can the input number be? If it's small enough, then you could just pre-calculate all the perfect sqaures and store them in a dictionary:

IDictionary<long, bool> squares = new Dictionary<long, bool>;
for(long i = 1; i*i <= MAX_NUM; ++i) {
    squares[i*i] = true;
}

Then, to find out if a number x is a perfect square, you just check squares[x] to see if it's true.

dcp
  • 54,410
  • 22
  • 144
  • 164
0

Something along the lines of this would work.

public Boolean IsSquare(double input)
{
    double root, product;
    Boolean isSquare,isGTInput;

    root = 1;
    product = 0;
    isSquare = false;
    isGTInput = false;

    while (!isSquare && !isGTInput)
    {
        product = root * root;
        if (product == input)
            isSquare = true;
        else if (product > input)
            isGTInput = true;

        root += 1;
    }

    return isSquare;

}
Kibbee
  • 65,369
  • 27
  • 142
  • 182