Anybody Knows the Logic To Find Out a Number is Perfect Square or not? [duplicate]

Question

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

Answer 1

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.