69.sqrt(x).md

69. Sqrt(x)

Test Cases

Normal Cases

Input: 4
Output: 2

Input: 1
Output: 1

Edge / Corner Cases

• x is not a perfect square.

Input: 2
Output: 1

Input: 8
Output: 2

Input: 12
Output: 3

• x is a large number which might cause overflow.

Input: 2147395599
Output: 46339

Binary Search

NOTE: The problem is looking for the square root of x rounded down to the nearest integer. If you are checking if a number is a perfect square, please check 633. Sum of Square Numbers or 367. Valid Perfect Square.

The sqrt is always in the range of 1..x, so we can apply the binary search to find the sqrt number, that is searching sqrt * sqrt = x, if x is a perfect square, then we find the sqrt number, otherwise, we find the largest number num which num * num <= x because we have to round down to the nearest integer.

x = 4
sqrt = 2

x = 8
sqrt = 2.8... round down to 2

1 * 1 = 1 <= 8  [O]
2 * 2 = 4 <= 8  [O] * answer
3 * 3 = 9  > 8  [X]
4 * 4 = 16 > 8  [X]

We can generalize the problem is to find the last number num which num * num <= x which num in 1..x, then we can apply the binary search to find the num.

x = 15, sqrt = 3.87... round down to 3

1, 2, 3, 4, 5, 6, ...
O, O, O, X, X, X...
      ^ // The largest number `num` which `num * num <= x`

Note: We should check sqrt = x / sqrt (num^2 <= target is equivalent to num <= target / num) to prevent overflow of sqrt * sqrt.

fun mySqrt(x: Int): Int {
    if (x == 0) return 0
    var left = 1
    var right = x

    while (left <= right) {
        val middle = left + (right - left) / 2
        if (valid(middle, x)) {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }   
    return right
}

private fun valid(middle: Int, x: Int): Boolean {
    // Original is `middle * middle <= x`
    // Equivalently, to prevent overflow:
    return middle <= x / middle
}

• Time Complexity: O(log n).
• Space Complexity: O(1).