C++で任意の2つの要素の差がkで割り切れるm個の要素のセットを見つける方法

問題の概要

N個の正の整数からなる配列と、変数Kが与えられたとします。この中から、任意の2つの要素の差がKで割り切れるような、ちょうどm個の要素のセットを見つける必要があります。

例えば、配列 A = [4, 7, 10, 6, 9]、k = 3、m = 3 の場合、出力は「Yes」になります。4、7、10 という3つの要素が条件を満たすからです。

解法のアプローチ

この問題を効率的に解く鍵となるのは、各要素を k で割った余り（剰余）に注目することです。同じ余りを持つ2つの要素の差は、必ず k で割り切れるという性質を利用します。

具体的な手順は以下のとおりです。

• サイズ k の2次元配列 rem[][] を作成します。インデックスが余りを表し、各要素には対応する余りを持つ元の配列の値を格納します。
• 配列を1回走査し、各要素を余りごとに分類します。
• 余りのグループを調べ、サイズが m 以上のグループが存在すれば、その中から任意の m 個の要素を選ぶことで条件を満たすセットが得られます。

C++での実装例

#include<iostream>
#include<vector>
using namespace std;
void searchElementsSet(int arr[], int n, int k, int m) {
   vector<int> rem_matrix[k];
   for (int i = 0; i < n; i++) {
      int rem = arr[i] % k;
      rem_matrix[rem].push_back(arr[i]);
   }
   for (int i = 0; i < k; i++) {
      if (rem_matrix[i].size() >= m) {
         cout << "Yes Possible"<<endl;
         for (int j = 0; j < m; j++)
            cout << rem_matrix[i][j] << " ";
         return;
      }
   }
   cout << "Impossible";
}
int main() {
   int arr[] = {4, 7, 10, 6, 9};
   int k = 3;
   int m = 3;
   int n = sizeof(arr) / sizeof(arr[0]);
   searchElementsSet(arr, n, k, m);
}

出力結果

Yes Possible
4 7 10

計算量

このアルゴリズムの時間計算量は O(n)、必要な追加メモリの空間計算量も O(n) です。配列を1回走査して余りごとに分類するだけなので、非常に効率的な手法と言えます。

まとめ

「差がkで割り切れる要素の集合を見つける」という一見複雑な問題も、剰余に着目して要素をグループ化することでシンプルに解決できます。同じ余りのグループ内の要素同士は必ず条件を満たすため、グループのサイズが m 以上かどうかを確認するだけで答えが求まります。