Pular para o conteúdo

Raiz quadrada inteira

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

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

Tempo-alvo
O(log n)
Espaço-alvo
O(1)

Restrições

  • n is a non-negative integer

Travou na ideia, e não no código? Busca binária explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado