### View *Sqrt(x)* on LeetCode

## Statistics

**Time Spent Coding**

5 minutes

**Time Complexity**

O(n) - In the worst case, we must loop ≈ x//2 times through the while loop, but big O complexity represents the growth of the time complexity relative to n, which remains liner with or without the multiple, resulting in the O(n) time complexity.

**Space Complexity**

O(1) - The number of variables created is constant and does not depend on the input, resulting in the O(1) space complexity.

## Explanation

The code follows the standard algorithm to evaluate a square root but changes two things to follow the requirements of the problem correctly.

In the standard algorithm, we must iterate until the root’s precision is too large to differentiate from the last iteration. Ours implements floor division (`//`

) instead of normal division and only iterates until the `root`

’s square is less than or equal to x.

Once it is less than or equal to x, we have reached the floored square root of x and can return `root`

.

## Algorithm Used

**Visual Example**

Square root algorithm, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11

class Solution:
def mySqrt(self, x: int) -> int:
if x == 0 or x == 1:
return x
root = x
while root * root > x:
root = (root + x // root) // 2
return root