Problema
La raíz cuadrada entera de n es su raíz cuadrada redondeada hacia abajo, es decir, el mayor entero r que cumple r × r ≤ n. Las funciones de raíz cuadrada de las bibliotecas trabajan con números de punto flotante y, con entradas grandes, pueden equivocarse por una unidad. Por eso debes calcularla solo con enteros, por ejemplo con una búsqueda binaria sobre las respuestas posibles.
Implementa integer_square_root(n).
Entrada
n: un entero no negativo.
Salida
Devuelve el mayor entero r tal que r × r ≤ n.
Restricciones
0 ≤ n ≤ 10^18
Ejemplos
Entrada:
n = 50
Salida esperada:
expected = 7
Entrada:
long long n = 50;
Salida esperada:
long long expected = 7;
Entrada:
long n = 50;
Salida esperada:
long expected = 7;
Explicación
7 × 7 = 49 ≤ 50, pero 8 × 8 = 64 > 50, así que la respuesta es 7.
Entrada:
n = 144
Salida esperada:
expected = 12
Entrada:
long long n = 144;
Salida esperada:
long long expected = 12;
Entrada:
long n = 144;
Salida esperada:
long expected = 12;
Explicación
144 es exactamente 12 × 12, así que la respuesta es 12.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
La respuesta está entre 0 y n, y r × r crece a medida que crece r, así que puedes partir el intervalo por la mitad en cada paso.
Pista 2
Para n grande, r × r puede desbordarse; compara r con n / r o limita la cota superior.
Pista 3
Comprueba a mano entradas pequeñas como 0, 1 y 3.
Complejidad esperada
tiempo O(log n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.