मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसमें विशिष्ट तत्व हैं। कार्य उन टपल्स की कुल संख्या गिनना है जिनका प्रोडक्ट समान हो।
यदि टपल (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*(n-1)/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 हैं।
