Raiz Digital

Problema

Some os dígitos de n. Se o resultado tiver mais de um dígito, some os dígitos novamente. Repita até restar apenas um dígito.

Implemente digital_root(n).

n: Um inteiro positivo.

Retorne o dígito final único.

1 ≤ n ≤ 10¹⁸

Exemplo 1

Entrada:
n = 999

Saída esperada:
expected = 9

Entrada:
long long n = 999;

Saída esperada:
long long expected = 9;

Entrada:
long n = 999;

Saída esperada:
long expected = 9;

9 + 9 + 9 = 27, depois 2 + 7 = 9.

Exemplo 2

Entrada:
n = 38

Saída esperada:
expected = 2

Entrada:
long long n = 38;

Saída esperada:
long long expected = 2;

Entrada:
long n = 38;

Saída esperada:
long expected = 2;

3 + 8 = 11, depois 1 + 1 = 2.

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

Dica 1

Somar dígitos repetidamente acaba reduzindo o número a um único dígito.

Dica 2

Você pode simular o processo de soma repetida até o valor ficar menor que 10.

Dica 3

Cuidado com entradas muito grandes; o processo é simples, mas as várias passagens pelos dígitos são o principal trabalho.

Complexidade esperada

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