在 C++ 中具有相同 Product 的元组
假设我们有一个包含不同元素的整数数组。任务是计算元组的总数,使它们都具有相同的产品。
如果元组是(a,b,c,d),那么如果这个元组跟在(a*b=c*d)之后就是有效的。例如,
输入1:
arr[]= {2,4,6,3}
输出:
8
说明:元组的总数是8,这些是(2634),(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,intn)将数组元素及其大小作为输入。并以(a*b=c*d)的形式返回具有相同乘积的元组数。
创建一个哈希图,使得键是对的乘积,值是这些对的频率。
迭代映射并计算具有相同产品的此类元组的数量。
示例
#includeusing namespace std; int countTuple(int *arr, int n) { map 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< 输出结果 8所有具有相同乘积元组的元组都是8个。