Problem
Repeatedly divide n by 2, dropping any remainder (integer division), until it becomes 1. Count how many divisions that takes.
Implement halve_until_one(n).
Input
n: A positive integer.
Output
Return the number of divisions.
Einschränkungen
1 ≤ n ≤ 1,000,000,000,000
Beispiele
Eingabe:
n = 20
Erwartete Ausgabe:
expected = 4Eingabe:
long long n = 20;
Erwartete Ausgabe:
long long expected = 4;Eingabe:
long n = 20;
Erwartete Ausgabe:
long expected = 4;Erläuterung
20 → 10 → 5 → 2 → 1 takes 4 divisions.
Eingabe:
n = 1
Erwartete Ausgabe:
expected = 0Eingabe:
long long n = 1;
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long n = 1;
Erwartete Ausgabe:
long expected = 0;Erläuterung
n is already 1, so no divisions are needed.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Zähle, wie oft du die Zahl durch zwei teilen kannst, bevor sie 1 wird.
Hinweis 2
Wiederholte Ganzzahldivision reicht hier aus; du musst die verworfenen Reste nicht speichern.
Hinweis 3
Stell sicher, dass du genau bei 1 aufhörst und nicht erst bei 0.
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.