Sqrt(x)

Условие

Дано неотрицательное целое число x, необходимо вычислить и вернуть его квадратный корень. Поскольку результат должен быть целым числом, десятичную часть следует отбросить.

Примеры

Input: 4

Output: 2

Input: 8

Output: 2

Explanation: Квадратный корень из 8 приблизительно равен 2.82842, так как результат должен быть целым числом, возвращаем 2.

Решение

fun mySqrt(x: Int): Int {
    // Если x равен 0 или 1, то квадратный корень равен самому x
    if (x == 0 || x == 1) return x

    // Устанавливаем левую и правую границы для бинарного поиска
    var left = 1
    var right = x
    var result = 0

    // Используем бинарный поиск для нахождения целочисленного квадратного корня
    while (left <= right) {
        // Находим середину текущего диапазона
        val mid = left + (right - left) / 2

        // Проверяем, если квадрат mid равен x
        if (mid == x / mid) {
            return mid // Возвращаем mid, так как это точный квадратный корень
        } else if (mid < x / mid) {
            // Если mid^2 меньше x, продолжаем поиск в правой половине
            left = mid + 1
            result = mid // Сохраняем текущее mid как возможный результат
        } else {
            // Если mid^2 больше x, продолжаем поиск в левой половине
            right = mid - 1
        }
    }

    // Возвращаем результат, который соответствует целочисленному квадратному корню
    return result
}

Временная сложность

O(log n), n = x, так как используется бинарный поиск.

Пространственная сложность

O(1), так как используется только фиксированное количество дополнительных переменных.