Saltar al contenido

Raíz cuadrada entera

Fácil#binary-search#monotonic-predicate~20 min

La misión

Problema

Dado un número entero no negativo, devuelve el mayor número entero cuyo cuadrado no lo supere. La parte fraccionaria se descarta en lugar de redondearse, así que un número que no es un cuadrado perfecto da el valor justo por debajo de su raíz real. No se permiten las funciones integradas de raíz cuadrada.

Ejemplos

Input:  n = 8
Output: 2
Por qué: 2 al cuadrado es 4 y 3 al cuadrado es 9, así que la respuesta se recorta a 2
Input:  n = 16
Output: 4
Por qué: un cuadrado perfecto devuelve su raíz exacta
Input:  n = 0
Output: 0
Por qué: caso límite: cero es su propia raíz

Pistas

0 / 3

Tiempo objetivo
O(log n)
Espacio objetivo
O(1)

Restricciones

  • n is a non-negative integer

¿Lo que te frena es la idea y no el código? Búsqueda binaria lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio