Fácil 3 resolvidos 100.0% de aceitação

Halve Until One

Count how many halvings bring a number down to 1.

O que você vai aprender

  • Repetir até uma condição ficar falsa
  • Contar as iterações
  • Usar divisão inteira

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.

Restrições

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

Exemplos

Exemplo 1
Entrada:
n = 20

Saída esperada:
expected = 4
Entrada:
long long n = 20;

Saída esperada:
long long expected = 4;
Entrada:
long n = 20;

Saída esperada:
long expected = 4;

Explicação

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

Exemplo 2
Entrada:
n = 1

Saída esperada:
expected = 0
Entrada:
long long n = 1;

Saída esperada:
long long expected = 0;
Entrada:
long n = 1;

Saída esperada:
long expected = 0;

Explicação

n is already 1, so no divisions are needed.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Conte quantas vezes você consegue reduzir o número dividindo por dois antes de ele virar 1.

Dica 2

Divisão inteira repetida basta aqui; não precisa guardar os restos descartados.

Dica 3

Certifique-se de parar exatamente quando o valor chegar em 1, não quando virar 0.

Complexidade esperada

tempo O(log n), espaço extra O(1)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

# Programador Linguagem Tempo Memória Avaliação da IA Solução
1 HJhettory Jurash Python 774 ms - 5/5 Ver código
2 LMLaura Mahlow Python 851 ms - 5/5 Ver código
3 KKKaneki Ken Python 880 ms - 5/5 Ver código

Aprenda com outros

Soluções da comunidade

Atenção: 3 soluções completas abaixo Tente resolver sozinho primeiro. Você ainda pode espiar o código de outros desenvolvedores e as avaliações da IA. Entre e resolva o desafio para participar da discussão.