Todos los desafíos
Fácil 0 resueltos 0% de aceptación

Raíz cuadrada entera

Encuentra el mayor número entero cuyo cuadrado no supera n, sin usar una función de raíz cuadrada.

Lo que aprenderás

  • Buscar en un intervalo de respuestas con búsqueda binaria
  • Comparar r × r con n sin desbordamiento
  • Evitar errores de redondeo de punto flotante

Problema

Ver original (inglés)

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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.