একটি পূর্ণসংখ্যা অ্যারে এবং একটি টার্গেট সম দেওয়া আছে। যেসব যোড়ার যোগফল টার্গেট সমের সমান, তাদের সংখ্যা গণনা করুন।
উদাহরণ
অ্যারে: [2, 8, 1, 5, 11], Sum = 10
যোড়া: (2,8) → আউটপুট: 1 (নোট: উদাহরণে ভুলে 13 লেখা আছে)
পদ্ধতিগুলো
১. ব্রুট ফোর্স O(n²)
for (i=0 to n-1)
for (j=i+1 to n-1)
if (arr[i]+arr[j]==sum) count++;
২. হ্যাশ ম্যাপ O(n)
unordered_map freq;
for (x : arr) {
count += freq[sum - x];
freq[x]++;
}
৩. সর্ট + টু পয়েন্টার O(n log n)
sort(arr);
int i=0, j=n-1;
while (iC++ বাস্তবায়ন (হ্যাশ ম্যাপ)
#include
using namespace std;
int Pair_Sum(int arr[], int size, int sum) {
unordered_map freq;
int count = 0;
for (int i = 0; i < size; i++) {
count += freq[sum - arr[i]];
freq[arr[i]]++;
}
return count;
}
int main() {
int arr[] = {2, 6, 1, 7, 9, 8};
int sum = 9;
int size = sizeof(arr)/sizeof(arr[0]);
cout << "Pairs with sum " << sum << ": " << Pair_Sum(arr, size, sum);
return 0;
}
দ্রষ্টব্য
হ্যাশ ম্যাপ পদ্ধতিতে ডুপ্লিকেট হ্যান্ডলিং স্বয়ংক্রিয়। টু-পয়েন্টার পদ্ধতিতে ডুপ্লিকেট হ্যান্ডলিং আলাদা করতে হয়।
