এই সমস্যাতে, আমাদের দুটি অ্যারে arr1[] এবং arr2[] দেওয়া আছে যেগুলো ইউনিক ভ্যালু ধারণ করে। আমাদের কাজ হল দুটি অ্যারের ওভারল্যাপিং সম বের করা।
অ্যারেগুলোর সব এলিমেন্ট ডISTINCT। এবং আমাদের যেসব এলিমেন্ট দুটি অ্যারেতেই কমন, তাদের যোগফল রিটার্ন করতে হবে।
উদাহরণ দেখি:
ইনপুট
arr1[] = {5, 4, 9, 2}, arr2[] = {6, 3, 9, 4}
আউটপুট
2
ব্যাখ্যা
দুটি অ্যারেতে কমন এলিমেন্টগুলো হল 9 এবং 4। যোগফল = 9 + 9 + 4 + 4 = 26
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল একটি অ্যারে (যেমন arr1[]) ট্রাভার্স করে প্রতিটি এলিমেন্টের জন্য অন্য অ্যারেতে ম্যাচিং ভ্যালু খুঁজে বের করা। যদি ম্যাচ পাওয়া যায়, তবে উভয় মান যোগফলে যোগ করা।
এই পদ্ধতিতে নেস্টেড লুপ লাগে, তাই টাইম কমপ্লেক্সিটি O(N2)।
আরেকটি দক্ষ পদ্ধতি হল হ্যাশিং ব্যবহার করা। একটি হ্যাশ টেবিল তৈরি করে দুটি অ্যারের ভ্যালু স্টোর করব এবং ফ্রিকোয়েন্সি কাউন্ট রাখব। তারপর ফ্রিকোয়েন্সি ২ থাকা ভ্যালুগুলো যোগ করে যোগফলের ডাবল রিটার্ন করব।
উদাহরণ
#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
