Giả sử chúng ta có một mảng với N số nguyên dương và một biến khác K. Chúng ta phải tìm đúng m-phần tử, sao cho hiệu số giữa hai phần tử bất kỳ bằng k. Vì vậy, nếu mảng là A =[4, 7, 10, 6, 9] và k =3 và m =3, thì kết quả đầu ra sẽ là "có". Như chúng ta có thể tìm thấy ba phần tử như 4, 7, 10.
Để giải quyết điều này, chúng ta phải theo dõi các phần dư, khi một phần tử được chia cho k. Bây giờ, hãy tạo một mảng đa chiều rem [] [] có kích thước k, chỉ số của nó hiển thị phần còn lại và các phần tử sẽ là các phần tử theo phần còn lại tương ứng của chúng khi chia cho k. Bây giờ bằng cách duyệt qua tập hợp phần dư, chúng ta có thể nhận được một tập hợp có kích thước lớn hơn hoặc bằng kích thước yêu cầu m nếu tồn tại. Và hiệu của bất kỳ phần tử nào của tập hợp đó sẽ chia hết cho k.
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);
} Đầu ra
Yes Possible 4 7 10