Pythonで配列内の1つの要素を除くすべての約数となる整数を見つける方法

問題の概要

数値の配列が与えられたとき、その中のちょうど1つの要素を除いた残りのすべての要素の約数となる整数Bを見つける問題です。ただし、配列内の全要素のGCD(最大公約数)は1ではないものとします。

たとえば、入力が {8, 16, 4, 24} の場合、出力は 8 になります。8は4以外のすべての要素(8・16・24)を割り切れる一方、4だけは割り切れないためです。

解法のアプローチ:累積GCDの活用

この問題は、プレフィックスGCD(前方からの累積最大公約数)とサフィックスGCD(後方からの累積最大公約数)を組み合わせることで効率的に解けます。

ある要素 i を除外した残り全体のGCDは、「i より前の要素たちのGCD」と「i より後の要素たちのGCD」のGCDとして求められます。この値が array[i] を割り切れないのであれば、それが求めていた答えです。

アルゴリズムの手順

1. n を配列のサイズとする
2. n が 1 の場合は array[0] + 1 を返す
3. サイズ n の配列 prefix と suffix を用意する
4. prefix[0] = array[0] とし、i = 1 から順に prefix[i] = gcd(array[i], prefix[i-1]) を計算する
5. suffix[n-1] = array[n-1] とし、i = n-2 から逆順に suffix[i] = gcd(suffix[i+1], array[i]) を計算する
6. 各インデックス i について、i を除外した残りのGCD(cur)を求める
   • i = 0 のとき:cur = suffix[1]
   • i = n-1 のとき:cur = prefix[n-2]
   • 上記以外:cur = gcd(prefix[i-1], suffix[i+1])
7. array[i] % cur != 0 であれば cur を返す(これが答え)
8. 最後まで見つからなければ 0 を返す

Pythonでの実装例

以下が実際の実装コードです。

from math import gcd

def getDivisor(array):
    n = len(array)
    if n == 1:
        return array[0] + 1

    prefix = [0] * n
    suffix = [0] * n

    # 前方からの累積GCD
    prefix[0] = array[0]
    for i in range(1, n):
        prefix[i] = gcd(array[i], prefix[i - 1])

    # 後方からの累積GCD
    suffix[n - 1] = array[n - 1]
    for i in range(n - 2, -1, -1):
        suffix[i] = gcd(suffix[i + 1], array[i])

    # 各要素を除外した場合のGCDをチェック
    for i in range(n):
        if i == 0:
            cur = suffix[i + 1]
        elif i == n - 1:
            cur = prefix[i - 1]
        else:
            cur = gcd(prefix[i - 1], suffix[i + 1])

        if array[i] % cur != 0:
            return cur

    return 0

array = [8, 16, 4, 24]
print(getDivisor(array))

入力

[8, 16, 4, 24]

出力

8

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。prefix と suffix を事前に計算しておくことで、任意の1要素を除外した場合のGCDを定数時間で取得できるのがポイントです。毎回GCDを再計算する素朴な O(n²) のアプローチに比べて、大幅に高速に動作します。