Implement int sqrt(int x).

Compute and return the square root of x.

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

OK, how hard can this be, right? just find the first integer n such that n * n <= x and (n+1) * (n + 1) > x. Well mathematically this is correct, but if we transfer this idea to a program directly, we may run into the following two problems:

  • Time Limit Exceeded (well the OJ has a time limit for this question. O(N) is not acceptable)
  • Integer Overflow! It is possible that n*n is greater than the limit of Java integer (from -2^31 to 2^31 – 1).

I was stuck. Then someone on the discussion board mentioned: Think about math back in elementary school. n * n <= x is equivalent to what? Stupid me, n <= x / n. So if we avoid using plus and multiplication in comparison, we can avoid the integer overflow problem using subtraction and division. And I think this idea can extend to other primitive types as well. For something like (a+b)/2 we could re-write as a/2 + b/2.

As for the time limit problem, we can consider two improvements:

  • The naive algorithm would go from 1 to x. This is not necessary. We can simply check from 0 to x/2. Why? Because when x > 4, (x/2)^2 is always larger then x.
  • Is it necessary that we must go for a linear search? It’s a sorted sequence from 1 to x/2 and we are trying to find a number with a certain property. And this reminds me of binary search.

With these three improvements,  we can solve this question efficiently.

Code on github:


Enhanced by Zemanta