মান लीজिए আমাদের একটি পূর্ণসংখ্যার অ্যারে আছে যাতে স্বতন্ত্র উপাদান রয়েছে। কাজ হল সেই টাপলগুলোর মোট সংখ্যা বের করা যাতে সকল টাপলের গুণফল একই থাকে।
যদি টাপলটি হয় (a, b, c, d), তবে এটি বৈধ হবে যদি (a*b = c*d) শর্তটি পূরণ করে। উদাহরণস্বরূপ,
ইনপুট-১
arr[] = {2, 4, 6, 3}
আউটপুট
8
ব্যাখ্যা
মোট ৮টি টাপল আছে যাদের গুণফল সমান: (2,6,3,4), (2,6,4,3), (6,2,3,4), (6,2,4,3), (3,4,2,6), (4,3,2,6), (3,4,6,2), (4,3,6,2)। এখানে a*b = c*d।
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের জন্য হ্যাশম্যাপ ব্যবহার করা হয় যেখানে সব যুগল উপাদানের গুণফল সংরক্ষণ করা হয়।
- অ্যারে এলিমেন্ট ইনপুট নিন।
countTuples(int *arr, int n)ফাংশনটি অ্যারে এবং এর আকার নেয় এবং সমান গুণফলযুক্ত টাপল সংখ্যা রিটার্ন করে।- হ্যাশম্যাপ তৈরি করুন যেখানে কী হবে যুগলের গুণফল এবং মান হবে সেই গুণফলের ফ্রিকোয়েন্সি।
- ম্যাপে ইটারেট করে সমান গুণফলযুক্ত টাপল গণনা করুন। প্রতিটি জোড়ার জন্য n*(n-1)/2 জোড়া থাকতে পারে এবং প্রতিটি জোড়ায় ৮টি পারমুটেশন সম্ভব।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int countTuple(int *arr, int n) {
map<int, int> mp;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
mp[arr[i] * arr[j]]++;
int ans = 0;
for (auto it : mp)
ans += (it.second * (it.second - 1) / 2) * 8;
return ans;
}
int main() {
int n = 4;
int arr[n] = {2, 4, 6, 3};
int res = countTuple(arr, n);
cout << res << " ";
return 0;
}
আউটপুট
8
সমান গুণফলযুক্ত সব টাপলের সংখ্যা ৮।
