고유한 요소를 포함하는 정수 배열이 있다고 가정해 보겠습니다. 작업은 모두 동일한 제품을 갖도록 튜플의 총 수를 계산하는 것입니다.
튜플이 (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*2에서 이러한 순열을 가질 수 있는 '4' 숫자가 있습니다. 따라서 모든 요소에 대해 n*(n1)/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입니다.