Pythonで配列を合計がkで割り切れるペアに分割できるか判定する方法

数値の配列と整数 k が与えられたとき、配列全体を「各ペアの合計が k で割り切れる」ようなペアに分割できるかどうかを判定する問題を考えてみましょう。

たとえば、arr = [5, 15, 6, 9]、k = 7 という入力の場合、出力は True になります。(5, 9) の合計は 14、(15, 6) の合計は 21 であり、どちらも 7 で割り切れるからです。

解法の考え方：剰余に注目する

この問題は、各要素を k で割った余り（剰余）に着目すると効率的に解けます。ポイントは次のとおりです。

• 合計が k で割り切れるペアは、「余りが r の要素」と「余りが k − r の要素」の組み合わせになる
• 余りが 0 の要素同士、および余りがちょうど k/2 の要素同士は、互いにペアを組む必要があるため、それぞれの個数が偶数でなければならない
• それ以外の余りについては、r と k − r の出現回数が一致していなければならない

アルゴリズムの手順

1. n を配列のサイズとする
2. n が奇数であれば、ペアに分割できないので False を返す
3. 各要素の余り (((array[i] mod k) + k) mod k) の出現回数を辞書に記録する
4. 再度すべての要素を走査し、次の条件をチェックする
   • 2 × remainder == k の場合：occurrences[remainder] が奇数なら False を返す
   • remainder == 0 の場合：occurrences[remainder] が奇数なら False を返す
   • 上記以外の場合：occurrences[remainder] と occurrences[k − remainder] が一致しなければ False を返す
5. すべてのチェックを通過すれば True を返す

なお、((array[i] % k) + k) % k という式を使うのは、負の数が含まれる場合でも必ず非負の剰余を得るためです。Python の % 演算子は正の除数に対して常に非負の結果を返しますが、この書き方は他言語へ移植する際にも安全です。

Pythonでの実装例

from collections import defaultdict

def solve(array, k):
    n = len(array)
    if n % 2 != 0:
        return False
    occurrences = defaultdict(lambda: 0)
    for i in range(n):
        occurrences[((array[i] % k) + k) % k] += 1
    for i in range(n):
        remainder = ((array[i] % k) + k) % k
        if 2 * remainder == k:
            # 余りが k/2 の要素同士でペアを組むため、個数は偶数である必要がある
            if occurrences[remainder] % 2 != 0:
                return False
        elif remainder == 0:
            # 余りが 0 の要素同士でペアを組むため、個数は偶数である必要がある
            if occurrences[remainder] & 1:
                return False
        else:
            # 余り r の要素と余り k-r の要素がペアになるため、個数が一致する必要がある
            if occurrences[remainder] != occurrences[k - remainder]:
                return False
    return True

arr = [5, 15, 6, 9]
k = 7
print(solve(arr, k))

入力

[5, 15, 6, 9], 7

出力

True

計算量

• 時間計算量：O(n) — 配列を2回走査するだけで済みます
• 空間計算量：O(min(n, k)) — 剰余ごとの出現回数を格納する辞書が必要です