Определение целой части квадратного корня числа

Условие

Метод принимает целое число n и возвращает его квадратный корень, отбрасывая дробную часть (без округления вверх).

Примеры:

• 9 → 3
• 4 → 2
• 5 → 2 (√5 ≈ 2.23, целая часть — 2)

class Sqrt {
    public int calculateSqrt(int n) {
        // TODO
    }
}

Ответ

Используйте бинарный поиск максимального x, для которого x² ≤ n. Умножайте в long, чтобы избежать переполнения int; отрицательный аргумент отклоняйте.

public int calculateSqrt(int n) {
    if (n < 0) throw new IllegalArgumentException("n < 0");
    long left = 0, right = n, answer = 0;
    while (left <= right) {
        long mid = left + (right - left) / 2;
        if (mid * mid <= n) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return (int) answer;
}

Для int n квадрат mid помещается в long. Время O(log n), память O(1). Значения 0 и 1 обрабатываются тем же алгоритмом; дробная часть не вычисляется.