Tous les défis
Facile 0 résolus 0 % de réussite

Racine carrée entière

Trouver le plus grand entier dont le carré ne dépasse pas n, sans utiliser de fonction racine carrée.

Ce que vous allez apprendre

  • Parcourir un intervalle de réponses par dichotomie
  • Comparer r × r à n sans dépassement de capacité
  • Éviter les erreurs d'arrondi des nombres à virgule flottante

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.