สมมติว่าเรามีอาร์เรย์ที่มีจำนวนเต็มบวก N และตัวแปร K อีกตัว เราต้องหาองค์ประกอบ m ให้ตรงกัน เพื่อให้ความแตกต่างระหว่างสององค์ประกอบใดๆ เท่ากับ k ดังนั้นหากอาร์เรย์คือ A =[4, 7, 10, 6, 9] และ k =3 และ m =3 เอาต์พุตจะเป็น "ใช่" เนื่องจากเราสามารถหาองค์ประกอบสามอย่างได้ เช่น 4, 7, 10
เพื่อแก้ปัญหานี้ เราต้องติดตามเศษที่เหลือ เมื่อองค์ประกอบถูกหารด้วย k ตอนนี้สร้างอาร์เรย์หลายมิติ rem[][] ขนาด k ดัชนีจะแสดงส่วนที่เหลือ และองค์ประกอบจะเป็นองค์ประกอบตามส่วนที่เหลือที่สอดคล้องกันเมื่อหารด้วย k ตอนนี้โดยการสำรวจเซตที่เหลือ เราจะได้ชุดที่มีขนาดมากกว่าหรือเท่ากับขนาดที่ต้องการ m หากมี และผลต่างขององค์ประกอบใด ๆ ของเซตนั้นจะหารด้วย k ลงตัว
ตัวอย่าง
#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
