# Sqrt(x) Leetcode Solution

Difficulty Level Easy
algorithms Binary Search coding Interview interviewprep LeetCode LeetCodeSolutions MathViews 7548

As the title says, we need to find the square root of a number. Let say the number is x, then Sqrt(x) is a number such that Sqrt(x) * Sqrt(x) = x. If the square root of a number is some decimal value, then we have to return the floor value of the square root.

`4`
`2`
`7`
`2`

## Approach(Pre-built functions)

The math library of C++ and lang.Math library of Java have the pre-built functions to return the square root of a number. We can apply floor() to avoid any decimal value.

### Algorithm

1. If the number is less than 2, return itself
2. Call the sqrt() function
3. Floor the value obtained
4. Print the result

### Implementation of Sqrt(x) Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

int mySqrt(int x)
{
if(x <= 1)
return x;
return floor(sqrt(x));
}

int main()
{
int x = 7;
cout << mySqrt(x) << '\n';
}
```

#### Java Program

```import java.lang.Math;

class sqrt_x
{
static int mySqrt(int x)
{
if(x <= 1)
return x;
return (int)Math.floor(Math.sqrt(x));
}

public static void main(String args[])
{
int x = 7;
System.out.println(mySqrt(x));
}
}
```
`2`

### Complexity Analysis of algorithm to find Sqrt(x)

#### Time Complexity

O(logN). The sqrt() function uses the Newton-Raphson method to calculate the square root of a number, which has a time complexity of O(logN).

#### Space complexity

O(1). Constant space is used for variables.

## Approach(Binary Search)

Here, we can apply binary search on a range of numbers starting from 1 going up to x / 2where x = given number. Here, we implement the binary search on a chosen sorted sequence instead of an array.

Right limit is set as x / 2 because for every number x, greater than 2, the floor of their square root will be less than x / 2. Depending on the result of the binary search, we can jump to the left or right halves of the original sample space.

### Algorithm

1. Create a binarySearch() function returning floor of sqrt(x)
2. Initialize variable ans to store the result
3. If the number is less than 2, return itself
4. Initialise left and right values as 1 and x / 2 respectively
5. Until left <= right:
• Find middle of this range, mid = left + right / 2
• In case square of mid is equal to x,  return it as it is the square root
• If square of mid is less than x, jump to the right half by setting left = mid + 1
• Otherwise, jump to the left half by setting right = mid – 1 and save this value in ans
6. Print the result

### Implementation of Sqrt(x) Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

int binarySearch(int x)
{
int left = 1 , right = x / 2 , mid , ans;
long temp;

while(left <= right)
{
mid = (left + (right - left) / 2);
temp = (long)mid * (long)mid;
//mid * mid can be large, so use long
if(temp == x)
return mid;
if(temp < x)
ans = mid , left = mid + 1;
else
right = mid - 1;
}
return ans;
}

int mySqrt(int x)
{
if(x <= 1)
return x;
return binarySearch(x);
}

int main()
{
int x = 7;
cout << mySqrt(x) << '\n';
}
```

#### Java Program

```import java.lang.Math;

class sqrt_x
{
static int binarySearch(int x)
{
int left = 1 , right = x / 2 , mid , ans = 0;
long temp;

while(left <= right)
{
mid = (left + (right - left) / 2);
temp = (long)mid * (long)mid;
//mid * mid can be large, so use long
if(temp == x)
return mid;
if(temp < x)
{
ans = mid;
left = mid + 1;
}
else
right = mid - 1;
}
return ans;
}

static int mySqrt(int x)
{
if(x <= 1)
return x;
return binarySearch(x);
}

public static void main(String args[])
{
int x = 7;
System.out.println(mySqrt(x));
}
}
```
`2`

### Complexity Analysis of algorithm to find Sqrt(x)

#### Time Complexity

O(logN), as the binary search keeps dividing the sample space to its half. In the worst case, it can make up to logN comparisons.

#### Space complexity

O(1). Again, constant space is used for variables.

Translate »