สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่มีองค์ประกอบที่แตกต่างกัน ภารกิจคือการนับจำนวนสิ่งอันดับทั้งหมดเพื่อให้มีผลิตภัณฑ์เดียวกันทั้งหมด
หากทูเพิลคือ (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.
แนวทางในการแก้ปัญหานี้ -
แนวคิดในการแก้ปัญหานี้คือเราจะใช้ hashmap สำหรับการคูณทั้งหมดเป็นคู่
วิธีนี้จะช่วยให้แน่ใจว่าคู่ทั้งหมดที่จัดเก็บไว้ในแผนที่มีการคูณเหมือนกัน
หลังจากสร้างแผนที่การคูณของทุกองค์ประกอบในอาร์เรย์ที่กำหนดแล้ว เราจะสำรวจดูในแผนที่ว่ามีกี่คู่ที่มีการคูณแบบเดียวกัน (a*b =c*d)
เนื่องจากจำนวนคู่ทั้งหมดสามารถนับเป็น n*(n-1)/2 และในหนึ่งคู่จะมีตัวเลข '4' ซึ่งสามารถมีได้สูงสุด 4*2 การเรียงสับเปลี่ยนดังกล่าว ดังนั้นสำหรับทุกองค์ประกอบ มันสามารถมี n*(n1)/2*8 คู่ในนั้น
-
รับอินพุตขององค์ประกอบอาร์เรย์
-
ฟังก์ชันจำนวนเต็ม countTuples(int *arr, int n) รับองค์ประกอบอาร์เรย์และขนาดเป็นอินพุต และส่งคืนจำนวน tuples ที่มีผลิตภัณฑ์เดียวกันในรูปแบบ (a*b =c*d)
-
การสร้าง hashmap เพื่อให้คีย์เป็นผลคูณของคู่และค่าเป็นความถี่ของคู่เหล่านั้น
-
วนซ้ำบนแผนที่และนับจำนวนของสิ่งอันดับดังกล่าวที่มีผลิตภัณฑ์เดียวกัน
ตัวอย่าง
#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
