অ্যারে-এ গুণফল উপস্থিত জোড়া গণনা C++-এ

একটি অ্যারে দেওয়া থাকলে, কতটি জোড়ার গুণফল সেই অ্যারেতে উপস্থিত থাকে তা গণনা করতে হবে।

উদাহরণ

ইনপুট: arr = [6, 2, 3, 1, 5, 10]

বৈধ জোড়া: (2,3)=6, (6,1)=6, (3,1)=3, (2,5)=10, (1,5)=5, (2,1)=2, (1,10)=10 → মোট 7টি

অ্যালগরিদম

1. সাধারণ (O(n³)): তিনটি নেস্টেড লুপ।
2. দক্ষ (O(n²)) - Hash Set:
   • সব উপাদান একটি unordered_set-এ রাখুন।
   • নেস্টেড লুপে সব জোড়ার গুণফল বের করুন।
   • সেটে খুঁজে পেলে কাউন্ট বাড়ান।

C++ কোড উদাহরণ (দুই পদ্ধতি)

#include <bits/stdc++.h>
using namespace std;

// Naive O(n³)
int countPairsNaive(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) {
            int prod = arr[i] * arr[j];
            for (int k = 0; k < n; k++)
                if (arr[k] == prod) { count++; break; }
        }
    return count;
}

// Efficient O(n²) with Hash Set
int countPairsEfficient(int arr[], int n) {
    unordered_set s(arr, arr + n);
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (s.count(arr[i] * arr[j])) count++;
    return count;
}

int main() {
    int arr[] = {6, 2, 3, 1, 5, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Naive: " << countPairsNaive(arr, n) << endl;
    cout << "Efficient: " << countPairsEfficient(arr, n);
    return 0;
}

ইনপুট

[6, 2, 3, 1, 5, 10]

আউটপুট

7