Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Ganzzahlige Quadratwurzel

Finde die größte ganze Zahl, deren Quadrat n nicht übersteigt, ohne eine Wurzelfunktion zu benutzen.

Das lernst du

  • Einen Bereich möglicher Ergebnisse mit binärer Suche durchsuchen
  • r × r mit n vergleichen, ohne dass ein Überlauf entsteht
  • Rundungsfehler von Gleitkommazahlen vermeiden

Problem

Die ganzzahlige Quadratwurzel von n ist die abgerundete Quadratwurzel, also die größte ganze Zahl r mit r × r ≤ n. Die Wurzelfunktionen der Standardbibliothek rechnen mit Gleitkommazahlen und können bei großen Eingaben um eins danebenliegen. Rechne deshalb nur mit ganzen Zahlen, zum Beispiel mit einer binären Suche über die möglichen Ergebnisse.

Implementiere integer_square_root(n).

Eingabe

n: Eine nicht negative ganze Zahl.

Ausgabe

Gib die größte ganze Zahl r zurück, für die r × r ≤ n gilt.

Einschränkungen

0 ≤ n ≤ 10^18

Beispiele

Beispiel 1
Eingabe:
n = 50

Erwartete Ausgabe:
expected = 7
Eingabe:
long long n = 50;

Erwartete Ausgabe:
long long expected = 7;
Eingabe:
long n = 50;

Erwartete Ausgabe:
long expected = 7;

Erläuterung

7 × 7 = 49 ≤ 50, aber 8 × 8 = 64 > 50, also lautet die Antwort 7.

Beispiel 2
Eingabe:
n = 144

Erwartete Ausgabe:
expected = 12
Eingabe:
long long n = 144;

Erwartete Ausgabe:
long long expected = 12;
Eingabe:
long n = 144;

Erwartete Ausgabe:
long expected = 12;

Erläuterung

144 ist genau 12 × 12, also lautet die Antwort 12.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Das Ergebnis liegt zwischen 0 und n, und r × r wächst mit r. Du kannst den Bereich also in jedem Schritt halbieren.

Hinweis 2

Bei großem n kann r × r überlaufen. Vergleiche stattdessen r mit n / r oder begrenze die obere Schranke.

Hinweis 3

Prüfe kleine Eingaben wie 0, 1 und 3 von Hand.

Erwartete Komplexität

Zeit O(log n), zusätzlicher Speicher O(1)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.