Pythonで逆階乗を求めるアルゴリズムと実装例を解説

逆階乗とは

ある数 a が与えられたとき、その階乗が a と等しくなる整数 n(n! = a)を求める問題を「逆階乗」と呼びます。階乗とは、n! = n × (n − 1) × (n − 2) × … × 1 と定義される演算です。該当する整数 n が存在しない場合は −1 を返します。

たとえば、入力が a = 120 の場合、5! = 120 となるため、出力は 5 になります。

解法のアプローチ

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

• カウンタ i を 0、num を 1 で初期化する
• 結果を格納するための空リスト L を用意する
• i が a 未満である間、次の処理を繰り返す
  • i に num の階乗を代入する
  • L の末尾に i を追加する
  • num を 1 増やす
• a が L に含まれていれば、「L 内でのインデックス + 1」を返す
• 含まれていなければ −1 を返す

実装例(Python)

import math

class Solution:
    def solve(self, a):
        i, num = 0, 1
        L = []
        while i < a:
            i = math.factorial(num)
            L.append(i)
            num += 1
        if a in L:
            return L.index(a) + 1
        else:
            return -1

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

入力

120

出力

5

より効率的な方法:連続除算によるアプローチ

上記の方法では、階乗の値をリストに蓄えていくため、大きな数に対してはメモリを余分に消費します。そこで、a を 1, 2, 3, … と順番に掛け合わせながら比較していくことで、リスト不要・少ない計算量で答えを求められます。

class Solution:
    def solve(self, a):
        n, fact = 1, 1
        while fact < a:
            n += 1
            fact *= n
        return n if fact == a else -1

ob = Solution()
print(ob.solve(120))  # 出力: 5
print(ob.solve(100))  # 出力: -1

この実装では、積が a を超えた時点でループを抜け、一致するかどうかだけを判定するため、非常にシンプルかつ高速に動作します。

注意点

• 0! = 1 であり 1! = 1 でもあるため、a = 1 の場合は答えが一意に定まりません(通常は 1 を返すのが一般的です)。
• 階乗は極めて急激に増加するため、答えとなる n は小さい値に収まります。この性質により、どちらの方法でも実用的な速度で計算できます。