m-तत्वों का समुच्चय खोजें जिसके किन्हीं दो तत्वों का अंतर k से विभाज्य हो C++ में

मान लीजिए हमारे पास N धनात्मक पूर्णांकों का एक ऐरे है, और एक अन्य चर K है। हमें ठीक m-तत्व खोजने हैं, जैसे कि किन्हीं दो तत्वों का अंतर k के बराबर हो। तो यदि ऐरे A = [4, 7, 10, 6, 9] है, और k = 3 और m = 3, तो आउटपुट "yes" होगा। क्योंकि हम 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