इस समस्या में, हमें दो सरणियाँ दी गई हैं arr1[] और arr2[] जिसमें अद्वितीय मान हैं। हमारा काम दो सरणियों का अतिव्यापी योग ज्ञात करना है।
सरणियों के सभी तत्व अलग हैं। और हमें उन तत्वों का योग वापस करना होगा जो दोनों सरणियों के लिए सामान्य हैं
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr1[] = {5, 4, 9, 2}, arr2[] = {6, 3, 9, 4} आउटपुट
2
स्पष्टीकरण
The elements that are present in both arrays are 9 and 4. The sum is 9 + 9 + 4 + 4 = 26
समाधान दृष्टिकोण
समस्या का एक आसान समाधान एक सरणी को arr1 [] कह रहा है और प्रत्येक तत्व के लिए जांचता है कि किसी अन्य सरणी में मिलान करने वाला मान है या नहीं। यदि वर्तमान मान से मेल खाने वाला कोई तत्व मिलता है, तो दोनों को योग मान में जोड़ें।
इस दृष्टिकोण के लिए लूप्स के नेस्टिंग की आवश्यकता होती है जो ऑर्डर O(N 2 की समय जटिलता की ओर ले जाता है) )।
समस्या को हल करने का एक अन्य तरीका हैशिंग का उपयोग करना है। हम एक हैश तालिका बनाएंगे और तालिका में दोनों सरणियों के मूल्यों को संग्रहीत करेंगे और तत्वों की आवृत्ति की गणना रखेंगे। फिर आवृत्ति आवृत्ति दो के साथ मान जोड़ें। योग मूल्य का दोगुना लौटाएं।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
int findCommonValSum(int A[], int B[], int n){
unordered_map<int,int> hashTable;
for(int i=0;i<n;i++){
if(hashTable.find(A[i])==hashTable.end())
hashTable.insert(make_pair(A[i],1));
else
hashTable[A[i]]++;
if(hashTable.find(B[i])==hashTable.end())
hashTable.insert(make_pair(B[i],1));
else
hashTable[B[i]]++;
}
int commSum = 0;
for(auto itr = hashTable.begin(); itr!=hashTable.end(); itr++){
if((itr->second)==2){
commSum += (itr->first);
}
}
return (commSum*2);
}
int main(){
int A[] = { 5, 4, 9, 2 };
int B[] = { 6, 3, 9, 4 };
int n = sizeof(A) / sizeof(A[0]);
cout<<"The sum of common values in the array are "<<findCommonValSum(A, B, n);
return 0;
} आउटपुट
The sum of common values in the array are 26