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