Raíz cuadrada entera
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
Probar cada candidato desde uno hacia arriba funciona, pero toma demasiados pasos con una entrada grande. Fíjate en cómo se relaciona la respuesta con los candidatos que la rodean.
Elevar al cuadrado es creciente, así que todo candidato por debajo de la respuesta pasa la prueba y todo candidato por encima falla. Los candidatos se dividen limpiamente en un bloque que pasa y otro que falla.
Busca en el rango que va de cero hasta el propio número. Prueba el candidato del medio elevándolo al cuadrado: si el cuadrado cabe, recuerda el candidato y sigue buscando en la parte superior; si no, descártalo junto con toda la parte superior. El último candidato recordado es la respuesta.
- Tiempo objetivo
- O(log n)
- Espacio objetivo
- O(1)
Restricciones
- n is a non-negative integer
Solución
La prueba “¿cabe mi cuadrado?” es monótona: se cumple para todo candidato hasta la respuesta y falla para todo candidato más allá, que es justo la estructura que necesita una búsqueda por mitades. Cada ronda eleva al cuadrado el candidato del medio y descarta la mitad del rango, y recuerda el candidato cada vez que pasa para que la respuesta final sobreviva. Comparar cuadrados en lugar de sacar una raíz mantiene todo en números enteros. El tiempo es O(log n) y el espacio es O(1).
def integer_sqrt(n):
low, high, best = 0, n, 0
while low <= high:
mid = (low + high) // 2
if mid * mid <= n: # mid fits, but something larger might too
best, low = mid, mid + 1
else:
high = mid - 1 # mid is too big, and so is everything above
return best
print(integer_sqrt(8)) # -> 2
print(integer_sqrt(16)) # -> 4
print(integer_sqrt(0)) # -> 0¿Lo que te frena es la idea y no el código? Búsqueda binaria lo explica.