Problema
A raiz quadrada inteira de n é a raiz quadrada arredondada para baixo, ou seja, o maior inteiro r com r × r ≤ n. As funções de raiz quadrada das bibliotecas trabalham com ponto flutuante e podem errar por uma unidade quando a entrada é grande. Por isso, calcule usando apenas inteiros, por exemplo com uma busca binária sobre as respostas possíveis.
Implemente integer_square_root(n).
Entrada
n: um inteiro não negativo.
Saída
Retorne o maior inteiro r tal que r × r ≤ n.
Restrições
0 ≤ n ≤ 10^18
Exemplos
Entrada:
n = 50
Saída esperada:
expected = 7
Entrada:
long long n = 50;
Saída esperada:
long long expected = 7;
Entrada:
long n = 50;
Saída esperada:
long expected = 7;
Explicação
7 × 7 = 49 ≤ 50, mas 8 × 8 = 64 > 50, então a resposta é 7.
Entrada:
n = 144
Saída esperada:
expected = 12
Entrada:
long long n = 144;
Saída esperada:
long long expected = 12;
Entrada:
long n = 144;
Saída esperada:
long expected = 12;
Explicação
144 é exatamente 12 × 12, então a resposta é 12.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
A resposta está entre 0 e n, e r × r cresce junto com r, então dá para cortar o intervalo pela metade a cada passo.
Dica 2
Para n grande, r × r pode estourar; compare r com n / r ou limite o extremo superior.
Dica 3
Confira à mão entradas pequenas como 0, 1 e 3.
Complexidade esperada
tempo O(log n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.