Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Raiz quadrada inteira

Encontre o maior número inteiro cujo quadrado não passa de n, sem usar uma função de raiz quadrada.

O que você vai aprender

  • Procurar a resposta em um intervalo com busca binária
  • Comparar r × r com n sem overflow
  • Evitar erros de arredondamento de ponto flutuante

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.