解説

問題の概要

正の整数 \(N\) が与えられる。\(N\) を十進法で表したときの各桁の数字の和（ラッキーナンバー）を求めよ。

アプローチ

最も簡単な方法は、\(N\) を文字列として読み込み、各文字を数字に変換して合計する方法です。文字 '0' から '9' の整数値は、文字コードから '0' を引くことで得られます。

あるいは、整数として読み込み、\(N \bmod 10\) で最下位桁を取り出し、\(N \leftarrow \lfloor N / 10 \rfloor\) で桁を削る操作を繰り返しても同じ結果が得られます。

擬似コード

sum ← 0
for each character c in N:
    sum ← sum + (c - '0')
print sum

正しさの証明

入力 \(N\) を十進表記で \(d_k d_{k-1} \cdots d_1 d_0\) とする（各 \(d_i\) は \(0\) 以上 \(9\) 以下の数字）。求める答えは \(S = \sum_{i=0}^{k} d_i\) である。

文字列法： 入力を文字列として読むと、\(i\) 番目の文字はちょうど数字 \(d_i\) に対応する。c - '0' は文字 c が表す数字の整数値を返すので、ループは各 \(d_i\) をちょうど一度ずつ加算する。したがって最終的な sum は \(S\) に等しい。

剰余法： \(N \bmod 10\) は \(N\) の最下位桁 \(d_0\) に等しく、\(\lfloor N / 10 \rfloor\) は最下位桁を除いた数である。各反復で現在の最下位桁を加算してから取り除くので、\(N = 0\) になるまでに全ての桁がちょうど一度ずつ加算される。よって合計は \(S\) に等しい。

どちらの方法でも、出力はラッキーナンバーの定義と一致する。

計算量

\(N \leq 10^9\) なので桁数は高々 \(10\) 桁。

• 時間計算量: \(O(\log_{10} N)\)、実質的には定数時間
• 空間計算量: 文字列として読む場合は入力自体に \(O(\log_{10} N)\)、それ以外は \(O(1)\) の補助空間

実装上の注意

• \(N\) は最大 \(10^9\) で 32bit 整数に収まるが、文字列として処理すれば桁数の制限を気にする必要がない。
• 引き分け・タイブレークに関する規定は本問題には存在しない（答えは一意に定まる）。