Tutte le sfide
Facile 3 risolte 100.0% di accettazione

Halve Until One

Count how many halvings bring a number down to 1.

Cosa imparerai

  • Ciclare finché una condizione diventa falsa
  • Contare le iterazioni
  • Usare la divisione intera

Problema

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.

Vincoli

1 ≤ n ≤ 1,000,000,000,000

Esempi

Esempio 1
Input:
n = 20

Output atteso:
expected = 4
Input:
long long n = 20;

Output atteso:
long long expected = 4;
Input:
long n = 20;

Output atteso:
long expected = 4;

Spiegazione

20 → 10 → 5 → 2 → 1 takes 4 divisions.

Esempio 2
Input:
n = 1

Output atteso:
expected = 0
Input:
long long n = 1;

Output atteso:
long long expected = 0;
Input:
long n = 1;

Output atteso:
long expected = 0;

Spiegazione

n is already 1, so no divisions are needed.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Conta quante volte puoi dimezzare il numero dividendo per due prima che diventi uno.

Suggerimento 2

Qui basta la divisione intera ripetuta; non serve tenere traccia dei resti scartati.

Suggerimento 3

Assicurati di fermarti esattamente quando il valore raggiunge uno, non quando diventa zero.

Complessità attesa

tempo O(log n), spazio aggiuntivo O(1)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

# Programmatore Linguaggio Tempo Memoria Voto dell'IA Soluzione
1 HJhettory Jurash Python 774 ms - 5/5 Vedi il codice
2 LMLaura Mahlow Python 851 ms - 5/5 Vedi il codice
3 KKKaneki Ken Python 880 ms - 5/5 Vedi il codice

Impara dagli altri

Soluzioni della community

Attenzione spoiler: 3 soluzioni complete sotto Prova prima a risolverla da solo. Puoi comunque sbirciare il codice degli altri sviluppatori e le recensioni AI. Accedi e risolvi la sfida per partecipare alla discussione.