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 = 4Input:
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 = 0Input:
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.