Pythonで数値を最小個数のデシバイナリ数に分解するプログラム

問題の概要

文字列形式で与えられた数値 n があるとします。このとき、その合計が n と等しくなるような「デシバイナリ数」の最小個数を求める必要があります。デシバイナリ数とは、各桁が 0 または 1 のみで構成される十進数のことです。

例えば、入力が n = "132" の場合、出力は 3 になります。これは、132 が 3 つのデシバイナリ数(10 + 11 + 111)の合計として表せるためです。

解法のアプローチ

この問題を解く鍵は、答えが n の中で最も大きい桁の数字になるという点に気づくことです。

なぜなら、ある桁の数字が d である場合、その桁の合計を d にするには少なくとも d 個のデシバイナリ数が必要だからです(デシバイナリ数の各桁は最大でも 1 しか寄与できません)。逆に、最大の桁の数字と同じ個数だけ用意すれば、すべての桁を必ずカバーできます。

以下の手順で解きます。

• result を 1 で初期化する
• 文字列 n の各文字 i について繰り返す
  • i が 0 または 1 以外の場合、result を result と i の最大値に更新する
• result を返す

実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(n):
    result = 1
    for i in n:
        if i not in {0,1}:
            result = max(result, int(i))
    return result

n = "132"
print(solve(n))

入力

132

出力

3

計算量について

時間計算量は O(len(n))、空間計算量は O(1) です。文字列を一度走査するだけで答えが求まるため、非常に効率的なアルゴリズムと言えます。