Fastest way to determine if a number is perfect square I'm looking for the fastest way to determine if a long value is a perfect square (i.e. its square root is another integer). I was asked this in an interview recently.

Here is the very simple and straightforward way I'm doing it now:

  private static boolean isSquare(long n) {
    int i = 1;
    for (;;) {
      if (n &lt; 0)
        return false;
      if (n == 0)
        return true;
      n -= i;
      i += 2;
    }
  }


Is there any better way by which we can do this or optimize this more?
It is indeed very simple and straightforward. The time complexity is however \$(O(\sqrt n)\$. A binary search variation will do it in \$O(\log n)\$ time. Along the lines of the pseudocode:

    while lo &lt; hi
        mid = lo + (hi - lo)/2
        square = mid * mid
        if square == n
            return true
        if square &lt; mid
            lo = mid
        else
            hi = mid
    return false


Depending on the expected magnitude of \$n\$ it may or may not worth the effort. In the interview setting (no restrictions on \$n\$) I would go for the binary search.



if inside a tight loop usually hurts performance. Consider

    while (n &gt; 0) {
        n -= i;
        i += 2;
    }
    return n == 0;