69. Sqrt(x) Leetcode Solution

Sqrt(x) Leetcode Problem :

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.

jump game leetcode

Sqrt(x) Leetcode Solution :

Constraints :

  • 0 <= x <= 2^31 – 1

Example 1:

  • Input: x = 8
  • Output: 2

Intuition :

We want to find the square root of a given non-negative integer x. Instead of using a traditional approach like repeatedly subtracting numbers until we reach 0 or using a library function, we’ll use a smarter method called “Binary Search.” Binary Search helps us quickly find the square root by repeatedly narrowing down the search range.

Approach :

  1. We first check if x is 0 or 1. If it is, we know that the square root of 0 and 1 is 0 and 1 respectively, so we directly return x.

  2. For any other value of x, we set up a search range between 1 and x. We initialize two variables start and end to represent the range.

  3. Now comes the clever part: We use a while loop to repeatedly divide the search range in half (Binary Search) to find the square root.

  4. In each iteration of the loop, we calculate the middle value mid using the formula¬†start + (end – start) / 2. This formula ensures that we don’t encounter any integer overflow when dealing with large values of x.

  5. Next, we calculate the square of mid and compare it with x.

  6. If the square of mid is greater than x, we know the square root lies in the lower half of the search range. So, we move the end pointer to the left to narrow down the search range.

  7. If the square of mid is equal to x, we have found the square root! So, we return mid as the answer.

  8. If the square of mid is less than x, we know the square root lies in the upper half of the search range. So, we move the start pointer to the right to continue the search.

  9. We repeat steps 4 to 8 until the start pointer becomes greater than the end pointer. At this point, we have found the floor value of the square root, and end holds that value.

  10. To ensure that we return the correct floor value of the square root, we round down the value of end to the nearest integer using the Math.round() method.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription