कार्य को देखते हुए एआर [i] + एआर [जे] जोड़े की अधिकतम संख्या की गणना करना है जो कि के द्वारा विभाजित हैं जहां एआर [] एन पूर्णांक युक्त एक सरणी है।
इस शर्त को देखते हुए कि एक विशेष सूचकांक संख्या का उपयोग एक से अधिक जोड़े में नहीं किया जा सकता है।
इनपुट
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 प्रकार के int में सरणी के आकार को संग्रहीत करें
-
फ़ंक्शन में MaxPairs() अनियंत्रित मानचित्र का उपयोग करता है और सरणी के प्रत्येक तत्व के लिए um[arr[i]%K] के रूप में मान को एक-एक करके बढ़ाता है।
-
पुनरावृति करें और हर संभव उम मूल्य प्राप्त करें।
-
यदि um मान शून्य है तो युग्मों की संख्या um[0]/2 हो जाएगी।
-
फिर न्यूनतम (um[a], um[Ka])
का उपयोग करके प्रत्येक um मान '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;
/*Iteration for all the number that are less than the hash value*/
for (auto it : um){
// If the number is 0
if (it.first == 0){
//Taking half since same number
count += it.second / 2;
if (it.first % 2 == 0){
um[it.first] = 0;
}
else{
um[it.first] = 1;
}
}
else{
int first = it.first;
int second = K - it.first;
// Check for minimal occurrence
if (um[first] < um[second]){
//Taking the minimal
count += um[first];
//Subtracting the used pairs
um[second] -= um[first];
um[first] = 0;
}
else if (um[first] > um[second]){
// Taking the minimal
count += um[second];
//Subtracting the used pairs
um[first] -= um[second];
um[second] = 0;
}
else{
//Checking if the numbers are same
if (first == second){
//If same then number of pairs will be half
count += it.second / 2;
//Checking for remaining
if (it.first % 2 == 0)
um[it.first] = 0;
else
um[it.first] = 1;
}
else{
//Storing the number of pairs
count += um[first];
um[first] = 0;
um[second] = 0;
}
}
}
}
return count;
}
//Main function
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