Pythonで数値が「異なる階乗の和」として表せるかを判定するプログラム

問題の概要

正の整数 n が与えられたとき、n を互いに異なる階乗の値(1!, 2!, 3! など)の和として表すことができるかどうかを判定する問題です。

たとえば、入力が n = 144 の場合を考えてみましょう。

4! + 5! = 24 + 120 = 144 となるため、この場合の出力は True になります。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. fact を 1 で初期化し、結果を格納するための空のリスト res を用意します。また、カウンタ x を 2 とします。

2. fact <= n である限り、以下を繰り返して n 以下のすべての階乗をリストに収集します。

   • res の末尾に fact を追加する
   • fact を fact * x で更新する
   • x を 1 増やす

3. 収集した階乗を大きい方から順に走査し、n >= res[i] であれば n からその階乗の値を引きます。

4. 最終的に n が 0 になっていれば True を返します。

大きな階乗から優先的に使っていくこの手法は「貪欲法」と呼ばれます。階乗の値は急激に増加するため、小さい階乗から詰めていくよりも、大きい側から処理する方が効率的かつ確実に判定できます。

実装例(Python)

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, n):
        fact = 1
        res = []
        x = 2
        while fact <= n:
            res.append(fact)
            fact = fact * x
            x += 1
        for i in range(len(res) - 1, -1, -1):
            if n >= res[i]:
                n -= res[i]
        return n == 0

ob = Solution()
print(ob.solve(144))

実行結果

入力:

144

出力:

True

コードのポイント

• 最初の while ループでは、1!(=1)、2!(=2)、3!(=6)、4!(=24)、5!(=120)…といった n 以下の階乗をすべてリストに格納しています。
• 2番目の for ループでは、大きい階乗から順に引き算を行うことで、同じ階乗を二度使うことを防ぎ、「異なる階乗の和」という条件を満たしています。
• 最後に残った n が 0 であれば、与えられた数を異なる階乗の組み合わせでちょうど表せたことになります。