Last updated on January 29th, 2025 at 02:41 am

Here, we see a Sqrt(x) LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Binary Search, Math

Companies

Apple, Bloomberg, Facebook

Level of Question

Easy

Sqrt(x) LeetCode Solution

1. Problem Statement

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.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Modified Binary Search. This pattern is used when the problem involves searching for a specific value or condition in a sorted or monotonic sequence, and the search space can be reduced iteratively by dividing it into halves.

In the C++ code, the binary search approach is explicitly used to find the square root of a number. In the Java, JavaScript, and Python implementations, the Newton-Raphson method is used, which is an iterative numerical approximation technique. While not strictly binary search, it still involves narrowing down the search space iteratively, making it conceptually similar to the Modified Binary Search pattern.

3. Code Implementation in Different Languages

3.1 Sqrt(x) C++

class Solution {
public:
    int mySqrt(int x) {
        long long s=0,e=INT_MAX,ans=0;
        while(s<=e){
            long long m=s+(e-s)/2;
            if(m*m<=x){
                ans=m;
                s=m+1;
            }
            else e=m-1;
        }
        return ans;        
    }
};

3.2 Sqrt(x) Java

class Solution {
    public int mySqrt(int x) {
    long r = x;
    while (r*r > x)
        r = (r + x/r) / 2;
    return (int) r;        
    }
}

3.3 Sqrt(x) JavaScript

var mySqrt = function(x) {
    r = x;
    while (r*r > x)
        r = ((r + x/r) / 2) | 0;
    return r;    
};

3.4 Sqrt(x) Python

class Solution(object):
    def mySqrt(self, x):
        r = x
        while r*r > x:
            r = (r + x/r) / 2
        return r

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log(n))	O(1)
Java	O(log(n))	O(1)
JavaScript	O(log(n))	O(1)
Python	O(log(n))	O(1)