[LeetCode] 69. Sqrt(x)
Implement
int sqrt(int x)
.
Compute and return the square root of x.
Thought process:
O(n) solution is trivial. The idea is to use binary search to get logarithmic time complexity. For this question, we are searching for the largest number that's less than or equal to sqrt(x).
Note: when comparing mid^2 with x, use division to avoid integer overflow.
Note: when comparing mid^2 with x, use division to avoid integer overflow.
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | public class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } int left = 1; int right = x; while (left + 1 < right) { int mid = left + (right - left) / 2; if (mid == x / mid) { return mid; } if (mid < x / mid) { left = mid; } else { right = mid; } } if (right <= x / right) { return right; } return left; } } |
Time complexity: O(logn).
Comments
Post a Comment