C ++でLCM（arr [i]、arr [j]）> min（arr [i]、arr [j]）となるように、配列内のペアをカウントします

正の整数の配列が与えられます。目標は、条件LCM（arr [i]、arr [j]）>最小（arr [i]、arr [j]）となるようなarr[]の要素のペアの数を見つけることです。つまり、ペアの要素の最小公倍数は、両方の最小公倍数よりも大きくなります。

注 −ペア（arr [i]、arr [j]）は（arr [j]、arr [i]）と同じです。 2回数えないでください。

例を挙げて理解しましょう。

入力 − 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]の場合にのみfalseになります。ペアは、固有の要素間で形成されます。配列の一意の要素の頻度を含む順序付けられていないマップを取得します。次に、類似した要素のペアをすべて削除します。各周波数の最大ペアを（freq *（freq-1）/ 2）として計算します。そのような計算をすべて追加してカウントします。

配列全体にはサイズ要素があり、最大ペア=size（size-1）/2です。

結果はペアカウントになります。 （すべてのペア-同じ要素を持つペア）。

整数の配列を取ります。

• 整数の配列を取ります。

• 関数conditional_pair（int arr []、int size）は、配列とそのサイズを取得し、条件が満たされるようにペアの数を返します。

• 初期カウントを0とします。

• arr[]の要素とその頻度についてはunordered_mapumを取ります。

• 各周波数のforおよびforを使用してマップをトラバースしますtemp=it.second; （it =iterator）カウントするtemp *（temp-1）/2を追加します。要素の一時的な数のすべての可能なペア。

• これで、countには、この場合は考慮されない同じ要素のすべてのペアが含まれます。

• 配列要素の可能なペアの合計をtemp=size *（size-1）/2として計算します。

• countをcountとして更新-temp。

• 結果としてカウントを返します。

例

#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