Dividir por dois ou subtrair um
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
A resposta recursiva natural é um mais a resposta para o próximo número. Conte o quão profunda a pilha de chamadas fica para a maior entrada.
Reescreva a recursão para que o contador de passos vá junto como um argumento extra. Agora a chamada recursiva é a última coisa que a função faz.
Uma chamada que é a última ação pode ser substituída por reatribuir os argumentos e voltar ao início: um loop que atualiza n e o contador até n ser zero.
- Tempo-alvo
- O(log n)
- Espaço-alvo
- O(1)
Restrições
- 0 ≤ n ≤ 2¹⁰⁰⁰
Solução
Com um acumulador, a recursão vira uma chamada de cauda: a resposta para n é a resposta para o próximo número com o contador aumentado em um, e não sobra nada a fazer depois que a chamada retorna. O Python não elimina chamadas de cauda sozinho, então a chamada é transformada em um loop que reatribui n e o contador, e a pilha nunca cresce. A contagem também tem uma fórmula fechada para n acima de zero: um passo por dígito binário depois do primeiro, mais um por bit ligado (set bit). O tempo é O(log n) passos, e o espaço é O(1) além do próprio número.
def steps_to_zero(n):
# tail-recursive shape: steps(n, done) = done if n == 0 else steps(next n, done + 1)
done = 0
while n: # the tail call, as a loop
n = n // 2 if n % 2 == 0 else n - 1
done += 1
return done
print(steps_to_zero(14)) # -> 6
print(steps_to_zero(2 ** 1000)) # -> 1001
print(steps_to_zero(0)) # -> 0Travou na ideia, e não no código? Chamadas de cauda e loops explica isso.