leetcode/kotlin/0069-sqrtx.kt at main · neetcode-gh/leetcode · GitHub

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
* Binary Search
*/
class Solution {
    fun mySqrt(x: Int): Int {
        var left = 0L
        var right = x.toLong()
        var res = 0L

        while (left <= right) {
            val mid = left + (right - left) / 2
            val midSq = mid * mid

            if (midSq > x) {
                right = mid - 1
            } else if (midSq < x) {
                left = mid + 1
                res = mid
            } else {
                return mid.toInt()
            }
        }

        return res.toInt()
    }
}

/*
* Newton's method
*/
class Solution {
    fun mySqrt(x: Int): Int {
        if (x == 0) return 0

        var i = x.toLong()
        while (i > x / i) {
            i = (i + x / i) / 2
        }

        return i.toInt()
    }
}