在 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