C++ का उपयोग करके दो सरणियों का ओवरलैपिंग योग खोजना

समस्या विवरण

इस समस्या में, हमें दो सरणियाँ arr1[] और arr2[] दी गई हैं जिनमें अद्वितीय मान होते हैं। हमारा कार्य दो सरणियों का ओवरलैपिंग योग खोजना है।

सरणियों के सभी तत्व विशिष्ट हैं। और हमें उन तत्वों का योग वापस करना होगा जो दोनों सरणियों के लिए सामान्य हैं।

उदाहरण

इनपुट

arr1[] = {5, 4, 9, 2}
arr2[] = {6, 3, 9, 4}

आउटपुट

26

व्याख्या

दोनों सरणियों में मौजूद तत्व 9 और 4 हैं। योग = 9 + 9 + 4 + 4 = 26

हल का दृष्टिकोण

समस्या का एक सरल समाधान एक सरणी (arr1[]) को पार करना और प्रत्येक तत्व के लिए जांचना है कि क्या दूसरी सरणी में कोई मिलान मान है। यदि वर्तमान मान से मेल खाने वाला कोई तत्व मिलता है, तो दोनों को योग मान में जोड़ें।

इस दृष्टिकोण में लूप की नेस्टिंग की आवश्यकता होती है जिससे समय जटिलता O(N²) क्रम की होती है।

समस्या को हल करने का एक अन्य दृष्टिकोण हैशिंग का उपयोग करना है। हम एक हैश टेबल बनाएंगे और दोनों सरणियों के मानों को टेबल में संग्रहीत करेंगे और तत्वों की घटना आवृत्ति की गिनती रखेंगे। फिर घटना आवृत्ति दो वाले मान को जोड़ें। योग मान का दोगुना वापस करें।

C++ कार्यान्वयन

#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++) {
        hashTable[A[i]]++;
        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 << "सरणी में सामान्य मानों का योग है " << findCommonValSum(A, B, n);
    return 0;
}

आउटपुट

सरणी में सामान्य मानों का योग है 26

जटिलता विश्लेषण

• समय जटिलता: O(N) औसत स्थिति में
• स्पेस जटिलता: O(N)

वैकल्पिक दृष्टिकोण

यदि सरणियाँ क्रमबद्ध हैं, तो दो-पॉइंटर तकनीक O(N) समय और O(1) स्पेस में काम कर सकती है।