N개의 양의 정수가 있는 배열과 또 다른 변수 K가 있다고 가정합니다. 두 요소 간의 차이가 k와 같도록 정확히 m개의 요소를 찾아야 합니다. 따라서 배열이 A =[4, 7, 10, 6, 9]이고 k =3이고 m =3이면 출력은 "예"가 됩니다. 4, 7, 10과 같은 세 가지 요소를 찾을 수 있습니다.
이를 해결하려면 요소를 k로 나눌 때 나머지를 추적해야 합니다. 이제 크기가 k인 다차원 배열 rem[][]을 만듭니다. 인덱스는 나머지를 표시하고 요소는 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