Coding

LeetCode Sqrt(x) solution

0
(0)

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

  • 0 <= x <= 231 - 1

Solution

First I tried to understand the problem. What is asked is to return square root of a number and nearest lower integer to it in case the square root is not exact. Say for example for number 4, the square root would be 2. But for number 11, square root should be 3 as square of 3 is 9 which is lower than 11.

Then I gave a thought of how to solve this problem. One way is to emulate Long division method. But emulating Long Division into code would not be a trivial exercise. So thought through further. Another way could be to iterate from number 1 to number X and keep comparing if i*i is greater than X and then return that index i. I tried implementing the java code for that. Please see below.

public int mySqrt(int x) {
      if (x == 0) return 0;
      if (x == 1) return 1;
        
      for (int i=1; i<=x; i++) {          
          if(i>x/i) {
              return i-1;
          }
      }
      return 0;  
    }
}

And see time runtime and memory efficiency for this. You could derive that it is of O(N) time complexity and highly inefficient. It would definitely not make your leader at work or interviewer in panel happy.

I thought of optimizing it. Although it did not strike me directly, I saw some hint that binary search could be applied here. So the thought process of that solution would be that choose a left of 1. And a right of Integer Max value. Then find mid of left and right. Now if value of mid’s square is greater than X (your input number), then your result should lie between left and mid-1. Else your result should lie between mid+1 and right. And in the special case when mid square is less than or equal to x and (mid+1) square is greater than x, then your result would be mid. This way time complexity of finding square root of X is now of O(Log(X)).

Below is the java code implementation of this binary search approach.

 public int mySqrt(int x) {
        if (x == 0) return 0;
        int left = 1;
        int right = Integer.MAX_VALUE;
        int mid = left + (right-left)/2;
        
        while (true) {            
            if (mid>x/mid)  right = mid-1;
            else {
                if ((mid+1)>x/(mid+1)) return mid;
                else left = mid+1;
            }
            mid = left + (right-left)/2;
        }
        
    }

 

And above is the time and space efficiency result from LeetCode. While there is a third approach which could be even faster which is Integer division using Newton Method. But it will not strike you naturally or during an interview unless you are a Math major or an Apple has fallen on your head. 🙂 So I am not covering it here.

Lessons learnt while solving this problem

  • Just because a problem has been mentioned as LeetCode easy, don’t assume that it would be cakewalk. Some of the easy problems are also very tricky.
  • It is always good to solve a problem using brute force and then think of optimal ways.
  • While doing binary search, always think of the exit condition or the condition where you get the result and the loop exits.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?