এই সমস্যায়, আমাদেরকে দুটি অ্যারে দেওয়া হয়েছে 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
