Given a non-negative integer x, return the square root of x rounded down to the nearest integer. You may not use any built-in power or square root function such as pow(x, 0.5) or sqrt.
Example 1
Input: x = 4
Output: 2
Example 2
Input: x = 8
Output: 2
The real root is 2.828..., which rounds down to 2.
Constraints
- 0 <= x <= 2^31 - 1
Hints
Frequently asked at: Amazon, Microsoft, Apple, Bloomberg
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Counting up from 1 until the square passes x costs O(sqrt(x)), about 46,000 steps for the largest input. Notice the predicate k * k <= x is monotonic: true up to the answer and false after it. So we can binary search on the answer: keep a range of candidate roots and test the middle one. That needs only about 32 steps.
Algorithm
- Set
lo = 0,hi = x,ans = 0. - While
lo <= hi, computemidandsq = mid * midas a 64-bit number. - If
sq <= x,midis a valid answer: recordans = midand try larger withlo = mid + 1. - Otherwise
midis too big:hi = mid - 1. - Return
ans.
Time:
O(log x)Space: O(1)Interview tip: For
x = 2147483647 the product mid * mid overflows a 32-bit int. Use long (Java) or long long (C++). A good follow-up is Newton's method, which converges even faster.class Solution: def mySqrt(self, x: int) -> int: lo, hi, ans = 0, x, 0 while lo <= hi: mid = (lo + hi) // 2 if mid * mid <= x: ans = mid # mid works, try bigger lo = mid + 1 else: hi = mid - 1 # too big return ansCtrl + Enter runs the examples