Tuple với cùng một Sản phẩm trong C ++

Giả sử chúng ta có một mảng các số nguyên chứa các phần tử riêng biệt. Nhiệm vụ là đếm tổng số bộ giá trị sao cho chúng đều có cùng một sản phẩm.

Nếu tuple là (a, b, c, d), thì nó sẽ hợp lệ nếu tuple này theo sau (a * b =c * d). Ví dụ:

Đầu vào-1 :

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

Đầu ra :

8

Giải thích:Tổng số Tuples là 8 và đây là, (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) trong đó a * b =c * d.

Phương pháp giải quyết vấn đề này -

Ý tưởng là để giải quyết vấn đề này là chúng ta sẽ sử dụng một bản đồ băm cho tất cả các phép nhân theo cặp.

Điều này sẽ giúp đảm bảo rằng tất cả các cặp được lưu trữ trong bản đồ đều có cùng một phép nhân.

Sau khi tạo bản đồ phép nhân của mọi phần tử trong mảng đã cho, chúng ta sẽ duyệt qua bản đồ để kiểm tra xem có bao nhiêu cặp có cùng phép nhân ở dạng (a * b =c * d).

Vì tổng số cặp có thể được đếm là n * (n-1) / 2 và trong một cặp có số ‘4’ có thể có tối đa 4 * 2 nên hoán vị đó trong đó. Vì vậy, đối với mọi phần tử, nó có thể có, n * (n1) / 2 * 8 cặp trong đó.

• Nhận đầu vào của các phần tử mảng.

• Một hàm số nguyên countTuples (int * arr, int n) lấy phần tử mảng và kích thước của nó làm đầu vào. Và trả về số bộ giá trị có cùng sản phẩm ở dạng (a * b =c * d).

• Tạo một bản đồ băm sao cho khóa là sản phẩm của cặp và giá trị là tần suất của các cặp đó.

• Lặp lại bản đồ và đếm số lượng các bộ giá trị như vậy có cùng một sản phẩm.

Ví 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;
}

Đầu ra

8

Tất cả các bộ giá trị có cùng bộ giá trị sản phẩm là 8.