在 C++ 中計算陣列中滿足 LCM(arr[i], arr[j]) > min(arr[i],arr[j]) 的對數


給定一個正整數陣列。目標是找到 arr[] 元素對的數量,使得條件 LCM( arr[i], arr[j] ) > min( arr[i], arr[j] ) 成立。也就是說,一對元素的最小公倍數大於兩者中的最小值。

注意 - 對 ( 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。

結果將為 pairs-count。(所有對 - 具有相同元素的對)。

獲取一個整數陣列。

  • 獲取一個整數陣列。

  • 函式 conditional_pair(int arr[], int size) 獲取陣列及其大小,並返回滿足條件的對數。

  • 將初始計數設為 0。

  • 獲取 unordered_map<int, int> um 用於 arr[] 的元素及其頻率。

  • 使用 for 遍歷對映,對於每個頻率 temp = it.second;(it=迭代器)將 temp*(temp-1)/2 新增到計數中。temp 個元素的所有可能對。

  • 現在 count 包含所有相同元素的對,在我們的案例中將不考慮這些對。

  • 計算陣列元素的總可能對數為 temp=size*(size-1)/2。

  • 將 count 更新為 count - temp。

  • 返回 count 作為結果。

示例

 即時演示

#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

更新於: 2020-12-02

200 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告