Tuple ที่มีผลคูณเท่ากันใน C++

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่มีองค์ประกอบที่แตกต่างกัน งานคือนับจำนวน tuple ทั้งหมดที่มีผลคูณเท่ากัน

ถ้า tuple คือ (a,b,c,d) จะถูกต้องก็ต่อเมื่อ tuple นี้เป็นไปตาม (a*b = c*d) ตัวอย่างเช่น

ตัวอย่างอินพุต

arr[] = {2, 4, 6, 3}

เอาต์พุต

คำอธิบาย

จำนวน Tuple ทั้งหมดคือ 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 สำหรับการคูณทุกคู่ ซึ่งจะช่วยให้มั่นใจได้ว่าคู่ทั้งหมดที่เก็บใน map มีการคูณเท่ากัน

หลังจากสร้าง map ของการคูณของทุกองค์ประกอบในอาร์เรย์ที่กำหนด เราจะวนลูปผ่าน map และตรวจสอบว่ามีคู่กี่คู่ที่มีการคูณเท่ากันในรูปแบบ (a*b = c*d)

เนื่องจากจำนวนคู่ทั้งหมดสามารถนับได้เป็น n*(n-1)/2 และในหนึ่งคู่มี '4' ตัวเลขซึ่งสามารถมีการเรียงสลับได้สูงสุด 4*2 แบบในนั้น ดังนั้นสำหรับทุกองค์ประกอบ สามารถมี n*(n-1)/2*8 คู่ได้

รับอินพุตองค์ประกอบของอาร์เรย์
ฟังก์ชัน integer countTuples(int *arr, int n) รับอาร์เรย์และขนาดเป็นอินพุต และคืนค่าจำนวน tuple ที่มีผลคูณเท่ากันในรูปแบบ (a*b = c*d)
สร้าง hashmap โดยที่ key คือผลคูณของคู่ และ value คือความถี่ของคู่นั้นๆ
วนลูปผ่าน map และนับจำนวน tuple ที่มีผลคูณเท่ากัน

ตัวอย่างโค้ด

#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;
}

ผลลัพธ์

Tuple ทั้งหมดที่มีผลคูณเท่ากันคือ 8