合計がkの倍数になるペアにリストを分割できるか判定するPythonプログラム

問題概要

数値のリスト nums と整数 k が与えられたとき、リストをペアに分割し、それぞれのペアの合計が k で割り切れるかどうかを判定するプログラムを作成します。

例えば、nums = [4, 7, 2, 5]、k = 6 の場合を見てみましょう。(4, 2) と (7, 5) というペアに分割すると、合計はそれぞれ 6 と 12 となり、どちらも 6 で割り切れます。したがって、この場合の出力は True になります。

解法のアプローチ

この問題は、各数値を k で割った余り(剰余)に着目することで、効率的に解くことができます。手順は以下の通りです。

• リストの要素数が奇数の場合、ペアが作れないため False を返す
• サイズ k のカウント配列を作成し、0 で初期化する
• リスト内の各数値 n について、count[n % k] を 1 ずつ増やす
• count[0](k の倍数である要素の個数)が奇数の場合は False を返す
• i を 1 から k // 2 までループし、count[i] と count[k - i] が一致しない場合は False を返す
• すべての条件を満たせば True を返す

剰余が i となる要素と剰余が k - i となる要素は足し合わせると k の倍数になるため、この2つのグループの個数が一致していれば、全体を条件を満たすペアに分割できるというわけです。

実装例

class Solution:
    def solve(self, nums, k):
        if len(nums) % 2:
            return False

        count = [0] * k
        for n in nums:
            count[n % k] += 1

        if count[0] % 2:
            return False

        for i in range(1, k // 2 + 1):
            if count[i] != count[k - i]:
                return False
        return True

ob = Solution()
nums = [4, 7, 2, 5]
k = 6
print(ob.solve(nums, k))

入力

[4, 7, 2, 5], 6

出力

True

補足：kが偶数の場合の注意点

k が偶数の場合、剰余がちょうど k / 2 となる要素同士でペアを組むことになります。そのため、厳密にはそのグループの個数も偶数である必要があります。上記のコードでは i == k - i となるケースのチェックが自己比較になってしまうため、必要に応じて以下のチェックを追加するとより安全です。

if k % 2 == 0 and count[k // 2] % 2:
    return False

計算量

この解法の時間計算量は O(n + k)、空間計算量は O(k) です。すべてのペアの組み合わせを試す総当たり法(O(n²))と比べて大幅に高速であり、要素数が多いリストでも実用的に動作します。