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:

x = 4
sqrt = 2

x = 8
sqrt = 2.8...

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

num^2 <= target -> num <= target / num

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

O, O, O, X, X, X...
      ^ // The largest number `num` which `num * num <= x`

Note: We should search sqrt = x / sqrt to prevent overflow of sqrt * sqrt.

fun mySqrt(x: Int): Int {
    // Special cases
    if (x == 0) return 0

    // We start from 1, not 0 in case of division by zero.
    var left = 1
    var right = x
    while (left <= right) {
        val middle = left + (right - left) / 2
        val sqrt = x / middle
        if (middle <= sqrt) {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }    
    return right 
}

// This is the correct idea but leads to overflow (WA).
fun mySqrt(x: Int): Int {
    var left = 1
    var right = x
    while (left <= right) {
        val middle = left + (right - left) / 2
        val square = middle * middle
        if (square <= x) {
            left = middle + 1
        } else if (x < square) {
            right = middle - 1
        }
    }
    return right
}

Or we can find the last element that meets the conditions:

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