ধরা যাক আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে রয়েছে যাতে আলাদা উপাদান রয়েছে। কাজটি হল টিপলের মোট সংখ্যা গণনা করা যাতে তাদের সকলের একই পণ্য রয়েছে।
যদি টিপলটি (a,b,c,d) হয়, তাহলে এই টিপলটি অনুসরণ করলে এটি বৈধ হবে (a*b =c*d)। উদাহরণস্বরূপ,
ইনপুট-1 :
arr[]= {2,4,6,3} আউটপুট :
8
ব্যাখ্যা:মোট টিপলের সংখ্যা 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.
এই সমস্যা সমাধানের পদ্ধতি -
এই সমস্যাটি সমাধান করার ধারণাটি হল যে আমরা জোড়ায় সমস্ত গুণের জন্য একটি হ্যাশম্যাপ ব্যবহার করব৷
এটি নিশ্চিত করতে সাহায্য করবে যে মানচিত্রে সংরক্ষিত সমস্ত জোড়ার একই গুণ রয়েছে৷
প্রদত্ত অ্যারেতে প্রতিটি উপাদানের গুণনের মানচিত্র তৈরি করার পরে, আমরা মানচিত্রের মধ্য দিয়ে অতিক্রম করব তা পরীক্ষা করে দেখব, কতগুলি জোড়া রয়েছে যার (a*b =c*d) আকারে একই গুণ রয়েছে। পি>
যেহেতু জোড়ার মোট সংখ্যা n*(n-1)/2 হিসাবে গণনা করা যেতে পারে এবং একটি জোড়ায় '4' সংখ্যা রয়েছে যার মধ্যে সর্বাধিক 4*2 এই ধরনের পারমুটেশন থাকতে পারে। সুতরাং প্রতিটি উপাদানের জন্য, এতে n*(n1)/2*8 জোড়া থাকতে পারে।
-
অ্যারে উপাদানের ইনপুট নিন।
-
একটি পূর্ণসংখ্যা ফাংশন countTuples(int *arr, int n) অ্যারে উপাদান এবং এর আকার ইনপুট হিসাবে নেয়। এবং (a*b =c*d) আকারে একই পণ্য থাকা টিপলের সংখ্যা প্রদান করে।
-
একটি হ্যাশম্যাপ তৈরি করা যেমন কী হল জোড়ার গুণফল এবং সেই জোড়ার ফ্রিকোয়েন্সি হিসাবে মান।
-
মানচিত্রের উপর পুনরাবৃত্তি করা এবং একই পণ্যযুক্ত এই জাতীয় টিপলের সংখ্যা গণনা করা।
উদাহরণ
#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
একই পণ্যের টিপল সহ সমস্ত টিপল 8।
