Raiz quadrada inteira
A missão
Problema
Dado um número inteiro não negativo, retorne o maior inteiro cujo quadrado não passa dele. A parte fracionária é descartada, e não arredondada; assim, um número que não é um quadrado perfeito dá o valor logo abaixo da sua raiz real. Funções prontas de raiz quadrada não são permitidas.
Exemplos
Input: n = 8
Output: 2
Por quê: 2 ao quadrado é 4 e 3 ao quadrado é 9, então a resposta é truncada para 2
Input: n = 16
Output: 4
Por quê: um quadrado perfeito retorna a sua raiz exata
Input: n = 0
Output: 0
Por quê: edge case: zero é a sua própria raiz
Dicas
0 / 3
Testar cada candidato de um para cima funciona, mas leva passos demais para uma entrada grande. Repare em como a resposta se relaciona com os candidatos ao redor dela.
Elevar ao quadrado é uma operação crescente, então todo candidato abaixo da resposta passa no teste e todo candidato acima dela falha. Os candidatos se dividem certinho em um bloco que passa e um bloco que falha.
Busque no intervalo de zero até o próprio número. Teste o candidato do meio elevando-o ao quadrado: se o quadrado couber, lembre o candidato e continue procurando na parte de cima; caso contrário, descarte-o junto com toda a parte de cima. O último candidato lembrado é a resposta.
- Tempo-alvo
- O(log n)
- Espaço-alvo
- O(1)
Restrições
- n is a non-negative integer
Solução
O teste “o meu quadrado cabe?” é monotônico: ele vale para todo candidato até a resposta e falha para todo candidato além dela, que é exatamente a estrutura de que a busca binária precisa. Cada rodada eleva ao quadrado o candidato do meio e descarta metade do intervalo, lembrando o candidato sempre que ele passa, para que a resposta final sobreviva. Comparar quadrados em vez de tirar uma raiz mantém tudo em números inteiros. O tempo é O(log n) e o espaço é 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)) # -> 0Travou na ideia, e não no código? Busca binária explica isso.