Pythonで基数Kに変換した数値の桁の合計を求める方法

問題の概要

10進数（基数10）で表された数値 n と、別の基数 k が与えられたとします。このとき、n を基数10から基数 k に変換した後の各桁の合計を求める必要があります。桁の合計を計算する際には、各桁を通常の10進数として扱う点に注意してください。

例えば、入力が n = 985、k = 8 の場合を考えてみましょう。985 を8進数に変換すると「1731」になります。したがって、桁の合計は 1 + 7 + 3 + 1 = 12 となります。

解法のアルゴリズム

この問題は、基数変換の仕組みを利用することで簡単に解けます。手順は以下の通りです。

• 答えを格納する変数 ans を 0 で初期化します。
• n が k 以上である間、次の処理を繰り返します。
  • ans に「n を k で割った余り（n mod k）」を加算します。
  • n を「n を k で割った商」で更新します。
• ループ終了後、残った n の値を ans に加算します。
• ans を返します。

この方法では、基数変換の過程で現れる各桁を順番に取り出しながら合計していくため、効率的に桁の合計を求められます。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

def solve(n, k):
    ans = 0
    while n >= k:
        ans = ans + n % k
        n = n // k
    ans = ans + n
    return ans

n = 985
k = 8
print(solve(n, k))

入力

n = 985, k = 8

出力

12

コードの解説

このプログラムでは、% 演算子で余り（最下位の桁）を取り出し、// 演算子で整数除算によって桁を一つずつ削り落としていきます。ループが終わった時点で残る n は最上位の桁なので、それを最後に加算すれば全桁の合計が完成します。時間計算量は O(log_k n) であり、非常に効率的です。