Einfach 0 gelöst 0% Erfolgsquote

Integer Square Root

Find the largest whole number whose square does not exceed n, without a square root function.

Das lernst du

  • Search an answer range with binary search
  • Compare r × r with n without overflowing
  • Avoid floating point rounding errors

Problem

Übersetzung anzeigen

The integer square root of n is the square root rounded down: the largest integer r with r × r ≤ n. Library square roots work on floating point numbers and can be off by one for large inputs, so compute it with integers only, for example with a binary search over possible answers.

Implement integer_square_root(n).

Input

n: A non-negative integer.

Output

Return the largest integer r such that r × r ≤ n.

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 but 8 × 8 = 64 > 50, so the answer is 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 is exactly 12 × 12, so the answer is 12.

So gehst du vor

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

Hinweis 1

The answer lies between 0 and n, and r × r grows as r grows, so you can halve the range each step.

Hinweis 2

For large n, r × r can overflow; compare r with n / r instead, or cap the upper bound.

Hinweis 3

Check small inputs like 0, 1 and 3 by hand.

Erwartete Komplexität

O(log n) time, O(1) extra space

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.