デジタルルート

デジタルルート

各桁の数字を繰り返し合計し、1桁になるまで続けてください。

このチャレンジで学べること

整数 n の各桁の数字を合計してください。その結果が2桁以上の場合は、さらにその各桁の数字を合計します。これを1桁になるまで繰り返してください。

digital_root(n) を実装してください。

n: 正の整数。

最終的な1桁の数字を返してください。

1 ≤ n ≤ 10¹⁸

例 1

入力：
n = 999

期待される出力：
expected = 9

入力：
long long n = 999;

期待される出力：
long long expected = 9;

入力：
long n = 999;

期待される出力：
long expected = 9;

9 + 9 + 9 = 27、その後 2 + 7 = 9。

例 2

入力：
n = 38

期待される出力：
expected = 2

入力：
long long n = 38;

期待される出力：
long long expected = 2;

入力：
long n = 38;

期待される出力：
long expected = 2;

3 + 8 = 11、その後 1 + 1 = 2。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

桁の和を繰り返すと、最終的に1桁まで縮む。

ヒント 2

値が10未満になるまで、桁の合計を繰り返し求めればよい。

ヒント 3

非常に大きい入力に注意。処理自体は簡単だが、桁を何度も走査するのが主な作業になる。

目安の計算量

時間 O(d log n)、追加メモリ O(1)