Sqrt(x)

Hi Geeks! Welcome to 100 Days of Leetcode Challenge.

Day 5

Today we going to see about implementation of sqrt(x). Let’s jump into our given question,

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

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

Example 1:

Input: 4
Output: 2

Example 2:

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

Basic knowledge

How binary search works

To solve this sqrt(x) problem, you must have a basic knowledge of how binary search works.

I already made an article of Binary Search with Best Explanations. I recommend you to see this article.

How To approach this problem

The best way to solve this problem by using Binary Search. Binary search is the most popular Search algorithm. It works only with the sorted array.

Code WALK THROUGH

Consider the below example, we have to find the sqrt(8). So, initially we have

Now find the middle element, here it is 4.

Check if 4 is a sqrt of 8. How can we check that? Multiply 4 two times.

4 * 4 = 16; Since, it is greater than the 8.

So, we have to eliminate elements right to the 4.

Now the left most element we have is 1 and right most element is 4.

We have eliminated 5, 6, 7 and 8. Because it is greater than 8.

Now find the middle element, here it is 2 now.

Check if 2 is square root of 8, by multiplying 2 two times. 2 * 2 = 4; It gives 4.

Since, it is less than our square root element number 8.

So, the left most number becomes (mid + 1) i.e 3.

Now, find the middle element from 3 to 4., that is 3.

Check if 3 is square root of 8, by multiplying 3 two times. 3 * 3 = 9; It gives 9.

That’s already bigger than the 8.

What we need here? we need the number 8.

In this case, we have to return the number below to the mid element. That would be answer. It was the number 2.

We know, we already eliminated the number 2. So in this case, we have to subtract 1 from the middle element 3.

So return left – 1; That is 3 – 1 = 2.

Solution

JAVASCRIPT Program

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left = 1;
    let right = x;
    
    if(x < 2)
        return x;
    
    while(left < right)
    {
        let mid = left + Math.floor((right-left)/2);
        
        if(mid * mid == x)
            return mid;
        else if(mid * mid > x)
            right = mid;
        else
            left = mid + 1;
    }
    
    return left - 1;
};

Time Complexity : O(logn)

Since we have used binary search, it works with the time complexity of logn.

Space complexity : O(1)

Because, we didn’t used any additional arrays or lists to process the output.


0 thoughts on “Sqrt(x)”

  1. Pingback: 100 Days Leetcode Challenge – Passion of Programming

Leave a Comment

Your email address will not be published. Required fields are marked *