69. Sqrt(x)

Sqrt(x)

Problem Description

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

 

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

 

Constraints:

• 0 <= x <= 231 - 1

Approach) Binary Search

There are 3 possible ways to escape the loop.

1. when mid * mid is equal to x immediately return mid
2. when hi is smaller than lo
3. when hi is equal to lo

• Outside of the loop, hi is smaller or equal to lo
• Need to consider return value when hi === lo

e.g. x = 5

lo	mid	hi
0	2	5
3	4	5
3	-	3

at the out of the loop lo = hi = 3, however, it should return 2

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let lo = 0, hi = x;
    while (lo < hi) {
        const mid = parseInt((lo + hi)/2);
        if (mid * mid === x) {
            return mid;
        }
        if (x < mid * mid) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return x < hi * hi ? hi - 1 : hi; 
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 69. Sqrt(x)

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!