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.


2 thoughts on “Sqrt(x)

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s