Pythonで各桁の出現回数がその桁の値以下かどうかを判定する方法

ある数値 n が与えられたとき、「n の各桁が出現する回数が、その桁の値以下であるか」どうかを判定する問題を考えてみましょう。

例えば、入力が n = 5162569 の場合を考えてみます。この数値には「5」が2回、「1」が1回、「6」が2回、「2」が1回、「9」が1回含まれています。つまり、(5, 2)、(1, 1)、(6, 2)、(2, 1)、(9, 1) という組み合わせになり、すべての桁について出現回数が桁の値以下であるため、出力は True となります。

解決のためのアルゴリズム

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

• i を 0 から 9 まで順番に処理します。
  • temp に n を代入し、カウンタ cnt を 0 で初期化します。
  • temp が 0 になるまで、以下を繰り返します。
    • temp を 10 で割った余り（最下位の桁）が i と一致する場合、cnt を 1 増やします。
    • cnt が i より大きくなった時点で、False を返して処理を終了します。
    • temp を 10 で整数除算した商で更新し、次の桁へ進みます。
• すべての桁のチェックが完了したら、True を返します。

このアルゴリズムでは、各桁の出現回数を数えながら、途中で条件を満たさなくなった場合に即座に False を返すことで、無駄な計算を省いています。

実装例

それでは、上記のアルゴリズムを Python で実装してみましょう。

def solve(n):
    for i in range(10):
        temp = n
        cnt = 0
        while temp:
            if temp % 10 == i:
                cnt += 1
            if cnt > i:
                return False
            temp //= 10
    return True

s = 5162569
print(solve(s))

入力

5162569

出力

True

計算量について

このアルゴリズムの時間計算量は O(10 × d) です。ここで d は数値 n の桁数を表します。外側のループが固定の 10 回、内側のループが桁数分だけ回るため、非常に効率的に動作します。空間計算量も O(1) であり、追加のメモリをほとんど必要としない点も特徴です。