# Sqrt(x)
**Difficulty:** EASY
[External](https://leetcode.com/problems/sqrtx)
Canonical: https://scaleengineer.com/dsa/problems/sqrt(x)
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Infosys](https://scaleengineer.com/companies/infosys), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [tcs](https://scaleengineer.com/companies/tcs), [Citadel](https://scaleengineer.com/companies/citadel), [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## 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.

**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`

# Approaches
## Brute Force using Linear Search
This approach involves iterating through numbers starting from 1 and checking if their square is equal to or just exceeds the input `x`. The integer square root is the largest integer `i` for which `i*i <= x`.
**Time:** O(sqrt(x)) · **Space:** O(1)
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large values of `x`. It can lead to a "Time Limit Exceeded" error on online judges.
### Explanation
We can iterate with a variable `i` from 1 upwards. For each `i`, we compute its square. To avoid integer overflow when calculating `i*i` for large `i`, it's crucial to use a larger data type, like `long` in Java. The loop continues as long as `i*i <= x`. When the loop finds an `i` such that `i*i > x`, the previous integer, `i-1`, must be the integer square root of `x`.

```java
class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        for (long i = 1; i <= x; i++) {
            if (i * i > x) {
                return (int) (i - 1);
            }
            if (i * i == x) {
                return (int) i;
            }
        }
        return -1; // Should not be reached for non-negative x
    }
}
```
### Algorithm
*   Handle the edge case where `x` is 0. If `x` is 0, the square root is 0.
*   Initialize a loop counter `i` to 1. Use a `long` for `i` to prevent overflow during multiplication.
*   In each iteration, check if `i * i > x`.
*   If this condition is met, it means `(i-1)*(i-1) <= x` and `i*i > x`. Therefore, `i-1` is the answer. Return `(int)(i-1)`.
*   If `i * i == x`, then `i` is the perfect square root, return `(int)i`.
*   The loop will eventually terminate because for a large enough `i`, `i*i` will exceed `x`.

## Efficient Approach using Binary Search
A more efficient method is to use binary search. The problem is to find an integer `k` in the sorted range `[0, x]` such that `k*k <= x < (k+1)*(k+1)`. The function `f(k) = k*k` is monotonic, making binary search applicable.
**Time:** O(log x) · **Space:** O(1)
**Pros:** Significantly faster than linear search.; Guaranteed to find the solution within the time limits for the given constraints.
**Cons:** Slightly more complex to implement than the brute-force approach.
### Explanation
We are searching for the square root within the range of integers from `0` to `x`. We can apply binary search on this range. For any chosen number `mid`, if `mid*mid > x`, we know the actual square root must be smaller than `mid`, so we search in the left half. If `mid*mid <= x`, `mid` could be our answer, but there might be a larger integer whose square is also less than or equal to `x`, so we search in the right half.

```java
class Solution {
    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }
        long left = 1, right = x;
        int result = 0;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long midSquared = mid * mid;
            if (midSquared == x) {
                return (int) mid;
            } else if (midSquared < x) {
                // mid could be the answer, try for a larger one
                result = (int) mid;
                left = mid + 1;
            } else { // midSquared > x
                // mid is too large
                right = mid - 1;
            }
        }
        return result;
    }
}
```
### Algorithm
*   Handle edge cases: if `x` is 0 or 1, return `x`.
*   Initialize `left = 1` and `right = x`. These define our search space.
*   Loop as long as `left <= right`.
*   In each iteration, calculate the middle element `mid = left + (right - left) / 2`.
*   To prevent overflow, cast `mid` to `long` before squaring: `long square = (long) mid * mid;`.
*   If `square > x`, the answer lies in the left half. Set `right = mid - 1`.
*   If `square <= x`, `mid` is a potential answer. We store it and continue searching for a larger potential answer in the right half. Set `left = mid + 1`.
*   When the loop terminates (`left > right`), the stored result is the answer. An alternative is that `right` will hold the largest integer whose square is less than or equal to `x`.

## Optimal Approach using Newton's Method
Newton's method is a very fast numerical technique for finding successively better approximations to the roots of a function. To find `sqrt(x)`, we seek the root of the function `f(y) = y^2 - x`.
**Time:** O(log x) · **Space:** O(1)
**Pros:** Extremely fast, often the fastest method in practice.; Elegant and concise implementation.
**Cons:** The mathematical concept might be less intuitive than binary search for some.; Requires careful handling of integer division and potential overflows (using `long` helps).
### Explanation
The iterative formula for Newton's method is `y_{n+1} = y_n - f(y_n) / f'(y_n)`. For our function `f(y) = y^2 - x`, the derivative is `f'(y) = 2y`. Substituting these into the formula gives the recurrence relation: `y_{n+1} = (y_n + x / y_n) / 2`. We can start with an initial guess, for example `y_0 = x`, and iterate until the result converges. Since we are working with integers, the process will converge very quickly. The loop can terminate when our guess `y` squared is no longer greater than `x`.

```java
class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return (int) r;
    }
}
```
### Algorithm
*   Handle the edge case `x = 0`.
*   Initialize the guess `r` as a `long` with the value of `x`.
*   Loop as long as `r * r > x`.
*   In each iteration, update the guess using the formula: `r = (r + x / r) / 2`.
*   The loop terminates when `r*r <= x`. At this point, `r` is the integer part of the square root.
*   Return `r` cast to an `int`.

# Solutions
### CSharp

```csharp
public class Solution { public int MySqrt ( int x ) { int l = 0 , r = x ; while ( l < r ) { int mid = ( l + r + 1 ) >>> 1 ; if ( mid > x / mid ) { r = mid - 1 ; } else { l = mid ; } } return l ; } }
```

### Java

```java
class Solution {
public
  int mySqrt(int x) {
    int l = 0, r = x;
    while (l < r) {
      int mid = (l + r + 1) >>> 1;
      if (mid > x / mid) {
        r = mid - 1;
      } else {
        l = mid;
      }
    }
    return l;
  }
}

```

### JavaScript

```javascript
/** * @param {number} x * @return {number} */ var mySqrt = function (x) {
  let [l, r] = [0, x];
  while (l < r) {
    const mid = (l + r + 1) >> 1;
    if (mid > x / mid) {
      r = mid - 1;
    } else {
      l = mid;
    }
  }
  return l;
};

```

### CPP

```cpp
class Solution {
public:
  int mySqrt(int x) {
    int l = 0, r = x;
    while (l < r) {
      int mid = (l + r + 1ll) >> 1;
      if (mid > x / mid) {
        r = mid - 1;
      } else {
        l = mid;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def mySqrt(self, x: int) -> int: l, r = 0, x while l < r: mid = (l + r + 1) >> 1 if mid > x // mid: r = mid - 1 else: l = mid return l

```