양의 정수 배열이 제공됩니다. 목표는 조건 LCM( arr[i], arr[j] )> 최소값( arr[i], arr[j] )이 되도록 arr[] 요소 쌍의 개수를 찾는 것입니다. 즉, 쌍에서 요소의 최소 공배수는 두 요소의 최소값보다 큽니다.
참고 - 쌍( arr[i], arr[j] )은 ( arr[j],arr[i] )와 동일합니다. 두 번 계산하지 마십시오.
예를 들어 이해합시다.
입력 - arr[] =[ 1,5,4,2 ]
출력 − LCM(arr[i], arr[j])> min(arr[i],arr[j])이 − 6인 배열의 쌍 수
설명 − 총 6쌍은 −
Pair 1 (1,5) LCM is 5 > 1 Pair 2 (1,4) LCM is 4 > 1 Pair 3 (1,2) LCM is 2 > 1 Pair 4 (5,4) LCM is 20 > 4 Pair 5 (5,2) LCM is 10 > 2 Pair 6 (4,2) LCM is 4 > 2
입력 - arr[] =[ 3,3,6 ]
출력 − LCM(arr[i], arr[j])> min(arr[i],arr[j])이 − 2인 배열의 쌍 수
설명 − 총 2쌍은 −
Pair 1 (3,6) LCM is 6 > 3 Pair 2 (3,6) LCM is 6 > 3
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
위의 조건은 arr[i]==arr[j]인 경우에만 거짓입니다. 고유한 요소 간에 쌍이 형성됩니다. 배열의 고유한 요소 빈도를 포함하는 정렬되지 않은 맵을 가져옵니다. 이제 모든 유사한 요소 쌍을 제거합니다. 각 주파수에 대해 최대 쌍을 ( freq * (freq-1)/2 )로 계산합니다. 계산할 모든 계산을 추가합니다.
총 배열에는 크기 요소가 있고 최대 쌍=size(size-1)/2입니다.
결과는 쌍 수입니다. ( 모든 쌍 - 동일한 요소와 쌍).
정수 배열을 가져옵니다.
-
정수 배열을 가져옵니다.
-
conditional_pair(int arr[], int size) 함수는 배열과 배열의 크기를 가져와 조건이 충족되는 쌍의 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
arr[]의 요소와 해당 빈도에 대해 unordered_map
-
for 및 각 주파수 temp =it.second를 사용하는 트래버스 맵; (it=iterator) temp*(temp-1)/2를 추가하여 계산합니다. 요소의 임시 수에 대해 가능한 모든 쌍입니다.
-
이제 count에는 우리의 경우 고려되지 않을 동일한 요소의 모든 쌍이 있습니다.
-
배열 요소에 대해 가능한 총 쌍을 temp=size*(size-1)/2로 계산합니다.
-
카운트를 카운트로 업데이트 - 임시.
-
결과로 카운트를 반환합니다.
예
#include <bits/stdc++.h>
using namespace std;
int conditional_pair(int arr[], int size){
int count = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; i++){
um[arr[i]]++;
}
for (auto it : um){
int temp = it.second;
count = count + temp * (temp - 1) / 2;
}
int temp = (size * (size - 1)) / 2;
count = temp - count;
return count;
}
int main(){
int arr[] = { 4, 1, 7, 3, 2};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are:
"<<conditional_pair(arr, size);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are: 10