C++で合計がKで割り切れる配列内のペアを数える方法

整数型の要素からなる配列が与えられます。この課題では、配列から作成できるすべてのペアを列挙し、それぞれのペアの要素の合計を計算して、その合計が k で割り切れるかどうかを判定します。最終的に、条件を満たすペアの総数を求めます。

入力例と出力例

例1

入力 − int arr[] = {4, 1, 2, 0, 2}、int k = 2

出力 − 合計がkで割り切れるペアの数：6

説明 − 与えられた配列から作成できるペアは次のとおりです。(4, 1) = 5（2で割り切れない）、(4, 2) = 6（割り切れる）、(4, 0) = 4（割り切れる）、(4, 2) = 6（割り切れる）、(1, 2) = 3（割り切れない）、(1, 0) = 1（割り切れない）、(1, 2) = 3（割り切れない）、(2, 0) = 2（割り切れる）、(2, 2) = 4（割り切れる）、(0, 2) = 2（割り切れる）。したがって、合計がk=2で割り切れるペアは (4, 2)、(4, 0)、(4, 2)、(2, 0)、(2, 2)、(0, 2) の6組となります。

例2

入力 − int arr[] = {2, 4, 8, 6, 10}、int k = 4

出力 − 合計がkで割り切れるペアの数：4

説明 − 作成できるペアは次のとおりです。(2, 4) = 6（4で割り切れない）、(2, 8) = 10（割り切れない）、(2, 6) = 8（割り切れる）、(2, 10) = 12（割り切れる）、(4, 8) = 12（割り切れる）、(4, 6) = 10（割り切れない）、(4, 10) = 14（割り切れない）、(8, 6) = 14（割り切れない）、(8, 10) = 18（割り切れない）、(6, 10) = 16（割り切れる）。したがって、合計が4で割り切れるペアは (2, 6)、(2, 10)、(4, 8)、(6, 10) の4組です。

解法1：素朴なアプローチ（全探索）

まずは最も直感的な全探索（ナイーブなアプローチ）から見ていきましょう。

• 整数型の配列と整数変数kを入力として受け取り、配列のサイズを計算して関数に渡します。
• kで割り切れる合計を持つペアの個数を格納するための一時変数countを宣言します。
• i を 0 から配列のサイズまでループさせます。
• 内側のループで j を i + 1 から配列のサイズまでループさせます。
• ループ内で sum = arr[i] + arr[j] を計算し、sum % k == 0 であれば count を1増やします。
• count を返します。
• 結果を出力します。

この方法の時間計算量は O(n²) となるため、配列のサイズが大きくなると処理が遅くなります。

解法2：効率的なアプローチ（剰余の頻度を利用）

次に、剰余（余り）の分布を利用した効率的なアプローチを紹介します。2つの数の合計がkで割り切れるのは、「2つの数をkで割った余りの和が0またはkになる」場合と完全に一致します。この性質を利用すると、O(n + k) という高速な計算量で答えを求められます。

• 整数型の配列を入力として受け取り、配列のサイズを計算して関数に渡します。
• ペアの個数を格納する一時変数countを宣言します。
• kで割った余りは必ず 0 ～ k-1 の範囲に収まるため、サイズkの配列checkを作成し、各余りの出現回数を記録します。
• i を 0 から配列のサイズまでループし、temp = arr[i] % k として ++check[temp] でカウントを増やします。
• 余りが0の要素同士のペアの数は、組み合わせの公式より count = check[0] * (check[0] - 1) / 2 で求めます。
• i を 1 から k / 2 まで、かつ i != (k - i) の間ループし、count += check[i] * check[k - i] によって「余りi」と「余りk-i」の組み合わせを加算します。
• kが偶数の場合は、余りが k / 2 となる要素同士のペア count += check[k / 2] * (check[k / 2] - 1) / 2 を加算します。
• count を返して結果を出力します。

サンプルコード（素朴なアプローチ）

#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
    int count = 0;
    for(int i = 0; i < size; i++){
        for(int j = i+1; j < size; j++){
            int sum = arr[i] + arr[j];
            if(sum % k == 0){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {4, 1, 2, 0, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout<<"Count pairs in array whose sum is divisible by k are: "<<pair_k(arr, size, k);
    return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます。

Count pairs in array whose sum is divisible by k are: 6

サンプルコード（効率的なアプローチ）

#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
    int temp = 0;
    int count = 0;
    int check[k] = {0};
    for (int i = 0; i < size; i++){
        temp = arr[i] % k;
        ++check[temp];
    }
    count = check[0] * (check[0] - 1) / 2;
    for (int i = 1; i <= k / 2 && i != (k - i); i++){
        count = count + check[i] * (check[k - i]);
    }
    if (k % 2 == 0){
        count = count + (check[k / 2] * (check[k / 2] - 1) / 2);
    }
    return count;
}
int main(){
    int arr[] = {4, 1, 2, 0, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout<<"Count pairs in array whose sum is divisible by k are: "<<pair_k(arr, size, k);
    return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます。

Count pairs in array whose sum is divisible by k are: 6

まとめ

本記事では、配列内の合計がkで割り切れるペアの数を数える2つの方法を紹介しました。二重ループによる全探索は実装がシンプルですが O(n²) の計算量が必要です。一方、剰余の頻度を利用した効率的なアプローチでは O(n + k) で高速に求解できます。扱うデータ量が多い場合は、後者の手法を採用することをおすすめします。