Chúng ta được cung cấp một mảng các số nguyên dương. Mục đích là tìm số lượng các cặp phần tử của arr [] sao cho điều kiện LCM (arr [i], arr [j])> tối thiểu của (arr [i], arr [j]). Nghĩa là, bội số chung thấp nhất của các phần tử trong một cặp lớn hơn mức tối thiểu của cả hai.
Lưu ý - cặp (arr [i], arr [j]) giống với (arr [j], arr [i]). Đừng đếm nó hai lần.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - arr [] =[1,5,4,2]
Đầu ra - Đếm các cặp trong một mảng sao cho LCM (arr [i], arr [j])> min (arr [i], arr [j]) là - 6
Giải thích - Tổng số 6 cặp là -
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
Đầu vào - arr [] =[3,3,6]
Đầu ra - Đếm các cặp trong một mảng sao cho LCM (arr [i], arr [j])> min (arr [i], arr [j]) là - 2
Giải thích - Tổng số 2 cặp là -
Pair 1 (3,6) LCM is 6 > 3 Pair 2 (3,6) LCM is 6 > 3
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Điều kiện trên sẽ chỉ sai khi arr [i] ==arr [j]. Các cặp sẽ được hình thành giữa các phần tử duy nhất. Lấy một bản đồ không có thứ tự chứa tần số của các phần tử duy nhất của mảng. Bây giờ để loại bỏ tất cả các cặp phần tử tương tự. Tính cho mỗi tần số các cặp tối đa là (freq * (freq-1) / 2). Cộng tất cả các phép tính như vậy để đếm.
Tổng mảng có các phần tử kích thước thì các cặp tối đa =size (size-1) / 2.
Kết quả sẽ là số cặp. (Tất cả các cặp - các cặp có cùng phần tử).
Lấy một mảng các số nguyên.
-
Lấy một mảng các số nguyên.
-
Hàm condition_pair (int arr [], int size) nhận mảng và kích thước của nó và trả về số lượng các cặp sao cho điều kiện được đáp ứng.
-
Lấy số lượng ban đầu là 0.
-
Lấy unrdered_map
-
Bản đồ di chuyển bằng cách sử dụng cho và cho mỗi tần số temp =it.second; (it =iterator) Thêm temp * (temp-1) / 2 để đếm. Tất cả các cặp có thể có cho số lượng phần tử tạm thời.
-
Bây giờ số đếm có tất cả các cặp phần tử giống nhau sẽ không được xem xét trong trường hợp của chúng tôi.
-
Tính tổng các cặp có thể có cho các phần tử mảng dưới dạng temp =size * (size-1) / 2.
-
Cập nhật số đếm dưới dạng đếm - tạm thời.
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are: 10