เราได้รับอาร์เรย์ของจำนวนเต็มบวก เป้าหมายคือการหาจำนวนคู่ขององค์ประกอบของ arr[] ซึ่งเงื่อนไข LCM( arr[i], arr[j] )> ขั้นต่ำของ ( 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 ) เพิ่มการคำนวณดังกล่าวทั้งหมดเพื่อนับ
อาร์เรย์ทั้งหมดมีองค์ประกอบขนาดแล้วสูงสุด pairs=size(size-1)/2
ผลลัพธ์จะเป็นคู่นับ ( คู่ทั้งหมด - คู่ที่มีองค์ประกอบเดียวกัน )
หาอาร์เรย์ของจำนวนเต็ม
-
หาอาร์เรย์ของจำนวนเต็ม
-
ฟังก์ชัน conditional_pair(int arr[], int size) ใช้อาร์เรย์และขนาดของอาร์เรย์ และส่งคืนค่าจำนวนคู่เพื่อให้ตรงตามเงื่อนไข
-
นับเริ่มต้นเป็น 0
-
ใช้ unordered_map
-
แผนที่สำรวจใช้สำหรับและสำหรับอุณหภูมิความถี่แต่ละรายการ =it.second; (it=iterator) เพิ่ม temp*(temp-1)/2 เพื่อนับ คู่ที่เป็นไปได้ทั้งหมดสำหรับจำนวนองค์ประกอบชั่วคราว
-
ตอนนี้การนับมีองค์ประกอบเหมือนกันทุกคู่ที่จะไม่ถูกพิจารณาในกรณีของเรา
-
คำนวณคู่ที่เป็นไปได้ทั้งหมดสำหรับองค์ประกอบอาร์เรย์เป็น temp=size*(size-1)/2
-
อัพเดทนับเป็นการนับ - ชั่วคราว
-
ผลตอบแทนนับเป็นผลลัพธ์
ตัวอย่าง
#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
