Problème
La racine carrée entière de n est sa racine carrée arrondie à l'entier inférieur, c'est-à-dire le plus grand entier r tel que r × r ≤ n. Les fonctions racine carrée des bibliothèques travaillent sur des nombres à virgule flottante et peuvent se tromper d'une unité pour les grandes valeurs. Calculez-la donc uniquement avec des entiers, par exemple par recherche dichotomique sur les réponses possibles.
Implémentez integer_square_root(n).
Entrée
n : un entier positif ou nul.
Sortie
Renvoyez le plus grand entier r tel que r × r ≤ n.
Contraintes
0 ≤ n ≤ 10^18
Exemples
Entrée :
n = 50
Sortie attendue :
expected = 7
Entrée :
long long n = 50;
Sortie attendue :
long long expected = 7;
Entrée :
long n = 50;
Sortie attendue :
long expected = 7;
Explication
7 × 7 = 49 ≤ 50 mais 8 × 8 = 64 > 50, donc la réponse est 7.
Entrée :
n = 144
Sortie attendue :
expected = 12
Entrée :
long long n = 144;
Sortie attendue :
long long expected = 12;
Entrée :
long n = 144;
Sortie attendue :
long expected = 12;
Explication
144 vaut exactement 12 × 12, donc la réponse est 12.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
La réponse est comprise entre 0 et n, et r × r croît avec r, donc vous pouvez diviser l'intervalle par deux à chaque étape.
Indice 2
Pour un grand n, r × r peut déborder ; comparez plutôt r à n / r, ou limitez la borne supérieure.
Indice 3
Vérifiez à la main les petites valeurs comme 0, 1 et 3.
Complexité attendue
temps O(log n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.