[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.

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

Popular posts from this blog

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee

[LeetCode] 269. Alien Dictionary

[LeetCode] 631. Design Excel Sum Formula