Einfach 3 gelöst 100.0% Erfolgsquote

Halve Until One

Count how many halvings bring a number down to 1.

Das lernst du

  • Schleifen, bis eine Bedingung falsch ist
  • Durchläufe zählen
  • Ganzzahldivision verwenden

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

Beispiel 1
Eingabe:
n = 20

Erwartete Ausgabe:
expected = 4
Eingabe:
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.

Beispiel 2
Eingabe:
n = 1

Erwartete Ausgabe:
expected = 0
Eingabe:
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.

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

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 HJhettory Jurash Python 774 ms - 5/5 Code ansehen
2 LMLaura Mahlow Python 851 ms - 5/5 Code ansehen
3 KKKaneki Ken Python 880 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 3 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.