Pular para o conteúdo

Dividir por dois ou subtrair um

Fácil#tail-recursion#bit-counting~15 min

A missão

Problema

Comece com um número inteiro n maior ou igual a zero. Em um passo, divida-o por dois se ele for par, ou subtraia um se for ímpar. Retorne quantos passos são necessários para chegar a zero. O número pode ser tão grande quanto 2 elevado a 1000, então uma solução que faz uma chamada recursiva por passo vai ultrapassar o limite de recursão padrão do Python.

Exemplos

Input:  n = 14
Output: 6
Por quê: 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0
Input:  n = 2 ** 1000
Output: 1001
Por quê: 1000 divisões por dois chegam a 1, e uma subtração chega a 0
Input:  n = 0
Output: 0
Por quê: edge case: já está em zero, então nenhum passo é dado

Dicas

0 / 3

Tempo-alvo
O(log n)
Espaço-alvo
O(1)

Restrições

  • 0 ≤ n ≤ 2¹⁰⁰⁰

Travou na ideia, e não no código? Chamadas de cauda e loops explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado