Soma repetida dos dígitos
A missão
Problema
Pegue um número inteiro não negativo e some os seus dígitos decimais. Se o resultado tiver mais de um dígito, some os dígitos dele de novo, e continue até restar um único dígito. Retorne esse dígito, de preferência sem nenhum loop.
Exemplos
Input: n = 38
Output: 2
Por quê: 3 + 8 = 11, depois 1 + 1 = 2
Input: n = 99999
Output: 9
Por quê: os dígitos somam 45, e 4 + 5 = 9
Input: n = 0
Output: 0
Por quê: edge case: zero já tem um dígito só e é o único número que termina em 0
Dicas
0 / 3
Simular o processo é fácil. A pergunta interessante é se o dígito final pode ser previsto diretamente a partir do número.
Dez deixa resto um na divisão por nove, assim como toda potência de dez. Pense no que isso diz sobre um número e a soma dos seus dígitos.
Um número e a soma dos seus dígitos deixam o mesmo resto módulo nove, então o dígito final é determinado por n módulo 9. Mapeie resto zero para 9 nos números positivos e trate n igual a 0 à parte; a expressão 1 mais (n menos 1) módulo 9 faz os dois mapeamentos de uma vez.
- Tempo-alvo
- O(1)
- Espaço-alvo
- O(1)
Restrições
- n ≥ 0
Solução
Toda potência de dez é um a mais que um múltiplo de nove, então um número e a soma dos seus dígitos deixam o mesmo resto módulo nove, e esse resto sobrevive a cada rodada do processo. Portanto, o dígito final é o único dígito de 1 a 9 com o mesmo resto que n, que é 1 mais (n menos 1) módulo 9, sendo zero o único número que termina em 0. Nenhum loop é necessário. O tempo e o espaço são O(1).
def digit_root(n):
if n == 0:
return 0 # the only number whose digits sum to 0
return 1 + (n - 1) % 9 # digit sums preserve the remainder mod 9
print(digit_root(38)) # -> 2
print(digit_root(99999)) # -> 9
print(digit_root(0)) # -> 0
print(digit_root(9)) # -> 9Travou na ideia, e não no código? Aritmética modular explica isso.