Целочисленный квадратный корень из n - это квадратный корень, округлённый вниз, то есть наибольшее целое r, для которого r × r ≤ n. Библиотечные функции извлечения корня работают с числами с плавающей точкой и на больших входных данных могут ошибиться на единицу. Поэтому считайте только в целых числах, например двоичным поиском по возможным ответам.
Реализуйте integer_square_root(n).
Входные данные
n: неотрицательное целое число.
Выходные данные
Верните наибольшее целое r, такое что r × r ≤ n.
Ограничения
0 ≤ n ≤ 10^18
Примеры
Ввод:
n = 50
Ожидаемый вывод:
expected = 7
Ввод:
long long n = 50;
Ожидаемый вывод:
long long expected = 7;
Ввод:
long n = 50;
Ожидаемый вывод:
long expected = 7;
Пояснение
7 × 7 = 49 ≤ 50, но 8 × 8 = 64 > 50, поэтому ответ 7.
Ввод:
n = 144
Ожидаемый вывод:
expected = 12
Ввод:
long long n = 144;
Ожидаемый вывод:
long long expected = 12;
Ввод:
long n = 144;
Ожидаемый вывод:
long expected = 12;
Пояснение
144 - это ровно 12 × 12, поэтому ответ 12.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Ответ лежит между 0 и n, а r × r растёт вместе с r, поэтому на каждом шаге диапазон можно сокращать вдвое.
Подсказка 2
При больших n произведение r × r может переполниться; вместо этого сравнивайте r с n / r или ограничьте верхнюю границу.
Подсказка 3
Проверьте вручную небольшие входные данные, например 0, 1 и 3.
Ожидаемая сложность
время O(log n), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.