Sqrt(x)

 69. Sqrt(x)

Easy

7.1K

4.2K

Companies

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

My_Python:

class Solution:
    def mySqrt(self, x: int) -> int:
        
        for i in range(1,x+1):
            if i*i == x or (i*i<x and (i+1) * (i+1)>x):
                return i
        return 0

Other:
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        first, last = 1, x
        while first <= last:
            mid = first + (last - first) // 2
            if mid == x // mid:
                return mid
            elif mid > x // mid:
                last = mid - 1
            else:
                first = mid + 1
        return last            

My C++:

class Solution {
public:
    int mySqrt(int x) {
        for (long int i=1;i<=x;i++)
        if ( i*i == x || i*i < x && (i+1)*(i+1)>x)
        {
           
            long int result = i;
            return result;
        }
        return 0;
    }
Other C++
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
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.
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.
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.
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. (This and (start+end)/2) are equivalent mathematically)
Next, we calculate the square of mid and compare it with x.
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.
If the square of mid is equal to x, we have found the square root! So, we return mid as the answer.
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.
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.
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.
Complexity
Time complexity:
The time complexity of this approach is $O(logN)$. It's very efficient because Binary Search reduces the search range by half in each iteration, making the search faster.
Space complexity:
The space complexity is $O(1)$, which means the amount of extra memory used is constant, regardless of the input. We only use a few variables to store the search range and the middle value during the computation.
Code
class Solution {
public:
    int mySqrt(int x) {
        // For special cases when x is 0 or 1, return x.
        if (x == 0 || x == 1)
            return x;
        
        // Initialize the search range for the square root.
        int start = 1;
        int end = x;
        int mid = -1;
        
        // Perform binary search to find the square root of x.
        while (start <= end) {
            // Calculate the middle point using "start + (end - start) / 2" to avoid integer overflow instead of (start+end)/2
            mid = start + (end - start) / 2;
            
            // Convert mid to long to handle large values without overflow.
            long long square = static_cast<long long>(mid) * mid;
            
            // If the square of the middle value is greater than x, move the "end" to the left (mid - 1).
            if (square > x)
                end = mid - 1;
            else if (square == x)
                // If the square of the middle value is equal to x, we found the square root.
                return mid;
            else
                // If the square of the middle value is less than x, move the "start" to the right (mid + 1).
                start = mid + 1;
        }
        
        // The loop ends when "start" becomes greater than "end", and "end" is the integer value of the square root.
        // However, since we might have been using integer division in the calculations,
        // we round down the value of "end" to the nearest integer to get the correct square root.
        return static_cast<int>(std::round(end));
    }
};

or
class Solution {
public:
    int mySqrt(int x) {
        if (x == 0)
            return x;
        int first = 1, last = x;
        while (first <= last) {
            int mid = first + (last - first) / 2;
            // mid * mid == x gives runtime error
            if (mid  == x / mid)
                return mid;
            else if (mid > x / mid) {
                last = mid - 1;
            }
            else {
                first = mid + 1;
            }
        }