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.

Table of Contents

## Example

4

2

7

2

## Approach(Pre-built functions)

The * math* library of C++ and

**library of Java have the pre-built functions to return the square root of a number. We can apply**

*lang.Math***floor()**to avoid any decimal value.

### Algorithm

- If the number is less than 2, return itself
- Call the
**sqrt()**function - Floor the value obtained
- 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 / 2**where 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

- Create a
**binarySearch()**function returning floor of sqrt(x) - Initialize variable
**ans**to store the result - If the number is less than 2, return itself
- Initialise
**left**and**right**values as 1 and x / 2 respectively - 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**

- Find middle of this range,
- 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.