Pythonで巨大な数の順列が8で割り切れるかどうかを判定する方法

桁数が非常に多い巨大な数が文字列として与えられたとき、その数字を並べ替えてできる順列の中に8で割り切れるものが存在するかを判定する問題を考えてみましょう。

例えば、入力が input_num = "4696984" の場合、出力は「Divisible by eight(8で割り切れる)」となります。

解法のカギ:8の倍数の判定ルール

この問題を効率よく解くための重要なポイントは、次の数学的な性質です。

ある整数が8で割り切れる ⇔ その下3桁(末尾3桁)だけでできた数が8で割り切れる

これは、1000 = 125 × 8 と8の倍数であるため、下3桁より上の部分は必ず8の倍数になるからです。つまり、元の数が持つ数字の中から「8で割り切れる3桁の数」を1つでも組み立てられれば、残りの桁をその前に並べることで、全体として8で割り切れる順列が構成できます。

アルゴリズムの手順

以下の手順で問題を解きます。

1. 桁数が3未満の場合: 数値をそのまま、および反転したものについて8で割った余りを確認し、0であればTrue(割り切れる)を返します。どちらでもなければFalseを返します。
2. 桁の出現回数を記録: 長さ10の配列を用意し、各数字(0〜9)が出現する回数をカウントします。
3. 3桁の8の倍数を全探索: 104(最小の3桁の8の倍数)から999まで、8ずつ増やしながら各候補を調べます。
4. 組み立て可能性のチェック: 各候補について、必要な各桁の個数が手元にある数字の個数を超えていないかを確認します。超えていなければ、その候補は作成可能なのでTrueを返します。
5. すべての候補で作成できなければFalseを返します。

実装例(Python)

def solve(input_num):
    # 桁数が3未満の場合
    if len(input_num) < 3:
        if int(input_num) % 8 == 0:
            return True
        input_num = input_num[::-1]
        if int(input_num) % 8 == 0:
            return True
        return False

    # 各桁(0〜9)の出現回数をカウント
    temp_arr = [0] * 10
    for count in range(len(input_num)):
        temp_arr[int(input_num[count])] += 1

    # 3桁の8の倍数(104〜998)を順にチェック
    for count in range(104, 1000, 8):
        temp = count
        occurences = [0] * 10
        occurences[temp % 10] += 1
        temp //= 10
        occurences[temp % 10] += 1
        temp //= 10
        occurences[temp % 10] += 1

        # 必要な桁がすべて利用可能か確認
        temp = count
        if occurences[temp % 10] > temp_arr[temp % 10]:
            continue
        temp //= 10
        if occurences[temp % 10] > temp_arr[temp % 10]:
            continue
        temp //= 10
        if occurences[temp % 10] > temp_arr[temp % 10]:
            continue
        return True

    return False


if solve("4696984"):
    print("Divisible by eight")
else:
    print("Not divisible by eight")

入力

4696984

出力

Divisible by eight

計算量の評価

このアルゴリズムの計算量を見てみましょう。

• 桁数のカウント:O(N)(Nは入力の桁数)
• 8の倍数の走査:(1000 − 104) ÷ 8 ≒ 112個の候補を、それぞれ定数時間でチェック

したがって全体の計算量は O(N) となり、数百桁・数千桁といった巨大な数でも高速に判定できます。すべての順列を生成して確認する非現実的なアプローチ(N!通り)と比べて、圧倒的に効率的です。

まとめ

「8の倍数は下3桁で決まる」という性質を利用することで、巨大な数の順列が8で割り切れるかどうかを、全順列を試すことなく線形時間で判定できます。桁の出現回数を数えて3桁の8の倍数と照合するだけというシンプルな手法のため、競技プログラミングなどでも応用価値の高いテクニックです。