นับคู่ในอาเรย์ที่ LCM(arr[i], arr[j])

เราได้รับอาเรย์ของจำนวนเต็มบวก เป้าหมายคือหาจำนวนคู่ของสมาชิกของ arr[] ที่เงื่อนไข LCM(arr[i], arr[j]) > minimum of (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] คู่จะเกิดระหว่างสมาชิกที่ไม่ซ้ำกัน ใช้ unordered_map เก็บความถี่ของสมาชิกที่ไม่ซ้ำของอาเรย์ ตอนนี้เพื่อลบคู่สมาชิกเหมือนกันทั้งหมด คำนวณสำหรับแต่ละความถี่ คูาสูงสุดเป็น (freq * (freq-1)/2) บวกคำนวณทั้งหมดเข้า count

อาเรย์ทั้งหมดมี size สมาชิก ดังนั้นคูาสูงสุด = size(size-1)/2

ผลลัพธ์จะเป็น pairs - count (คู่ทั้งหมด - คู่ที่มีสมาชิกเหมือนกัน)

รับอาเรย์จำนวนเต็ม
ฟังก์ชัน conditional_pair(int arr[], int size) รับอาเรย์และขนาด คืนจำนวนคู่ที่เงื่อนไขเป็นจริง
กำหนด count เริ่มต้น 0
สร้าง unordered_map<int, int> um สำหรับสมาชิกของ arr[] และความถี่
เดินทางแมปด้วยลูป FOR สำหรับแต่ละความถี่ temp = it.second (it=iterator) บวก temp*(temp-1)/2 เข้า count คู่ทั้งหมดที่เป็นไปได้สำหรับ temp จำนวนสมาชิก
ตอนนี้ count มีคู่ของสมาชิกเหมือนกันทั้งหมดที่จะไม่นับในกรณีของเรา
คำนวณคู่ที่เป็นไปได้ทั้งหมดสำหรับสมาชิกอาเรย์เป็น temp=size*(size-1)/2
อัปเดต count เป็น count - temp
คืน count

ตัวอย่างโค้ด C++

#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

นับคู่ในอาเรย์ที่ LCM(arr[i], arr[j]) > min(arr[i],arr[j]) ใน C++

แนวทางที่ใช้ในโปรแกรม

ตัวอย่างโค้ด C++

เอาต์พุต