Cho mảng N số nguyên dương và K. Tìm đúng m phần tử sao cho hiệu bất kỳ hai phần tử chia hết cho k. Ví dụ A=[4,7,10,6,9], k=3, m=3 → "Yes Possible" (4,7,10).
Nhóm các phần tử theo phần dư chia k. Nếu một nhóm có kích thước ≥ m thì đó là tập cần tìm.
Ví dụ
#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); }
Kết quả
Yes Possible 4 7 10