C++ में K से विभाज्य योग वाले जोड़ों की संख्या को अधिकतम करना

दिया गया कार्य उन जोड़ों arr[i] + arr[j] की अधिकतम संख्या की गणना करना है जो K से विभाज्य हैं जहां arr[] N इंटीजर्स वाला एक ऐरे है।

दिया गया शर्त है कि एक विशेष इंडेक्स नंबर का उपयोग एक से अधिक जोड़े में नहीं किया जा सकता।

इनपुट

arr[] = {1, 2, 5, 8, 3}, K=2

आउटपुट

2

व्याख्या - वांछित जोड़े हैं: (0,2), (1,3) क्योंकि 1+5=6 और 2+8=10। दोनों 6 और 10, 2 से विभाज्य हैं।

वैकल्पिक उत्तर जोड़े हो सकते हैं: (0,4), (1,3) या (2,4), (1,3) लेकिन उत्तर वही रहता है, यानी 2।

इनपुट

arr[] = {1, 3, 5, 2, 3, 4}, K=3

आउटपुट

3

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण

• इंट टाइप के वेरिएबल n में ऐरे का आकार संग्रहीत करें
• फंक्शन MaxPairs() में अनऑर्डर्ड मैप का उपयोग करें और ऐरे के प्रत्येक एलिमेंट के लिए um[arr[i]%K] को एक से बढ़ाएं
• हर संभावित um वैल्यू को पुनरावृत्त करें और प्राप्त करें
• यदि um वैल्यू शून्य है तो जोड़ों की संख्या um[0]/2 हो जाएगी
• फिर हर um वैल्यू 'a' से जोड़े बनाए जा सकते हैं (um[a], um[K-a]) के न्यूनतम का उपयोग करके
• um वैल्यू से उपयोग किए गए जोड़ों की संख्या घटाएं

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int MaxPairs(int arr[], int size, int K) {
    unordered_map<int, int> um;
    for (int i = 0; i < size; i++) {
        um[arr[i] % K]++;
    }
    
    int count = 0;
    /* उन सभी नंबर्स के लिए पुनरावृत्ति जो हैश वैल्यू से कम हैं */
    for (auto it : um) {
        // यदि नंबर 0 है
        if (it.first == 0) {
            // आधा ले रहे हैं क्योंकि वही नंबर
            count += it.second / 2;
            um[it.first] = it.second % 2;
        } else {
            int first = it.first;
            int second = K - it.first;
            
            // न्यूनतम घटना के लिए जांचें
            if (um[first] < um[second]) {
                // न्यूनतम ले रहे हैं
                count += um[first];
                // उपयोग किए गए जोड़े घटाएं
                um[second] -= um[first];
                um[first] = 0;
            } else if (um[first] > um[second]) {
                // न्यूनतम ले रहे हैं
                count += um[second];
                // उपयोग किए गए जोड़े घटाएं
                um[first] -= um[second];
                um[second] = 0;
            } else {
                // जांचें कि क्या नंबर समान हैं
                if (first == second) {
                    // यदि समान हैं तो जोड़ों की संख्या आधी होगी
                    count += it.second / 2;
                    // शेष के लिए जांचें
                    um[it.first] = it.second % 2;
                } else {
                    // जोड़ों की संख्या संग्रहीत करना
                    count += um[first];
                    um[first] = 0;
                    um[second] = 0;
                }
            }
        }
    }
    return count;
}

// मुख्य फंक्शन
int main() {
    int arr[] = {3, 6, 7, 9, 4, 4, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout << "Maximize the number of sum pairs which are divisible by K is: " << MaxPairs(arr, size, K);
    return 0;
}

आउटपुट

Maximize the number of sum pairs which are divisible by K is: 3