กำหนดอาร์เรย์ ar ที่มีตัวเลขบวกและอาร์เรย์ GCD[] ที่มีค่า gcd เป้าหมายคือการค้นหาจำนวนชุดย่อยขององค์ประกอบของ arr[] ที่มีค่า gcd ตามที่กำหนดใน GCD[]
ตัวอย่าง
อินพุต
arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5} ผลลัพธ์
Count of number of subsets of a set with GCD equal to a given number are: 1 2 2
คำอธิบาย
The subsets with GCD equal to 2 is [ 10, 6 ]. Subsets with GCD equal to 3 is [ 3 ], [ 6,3 ] Subsets with GCD equal to 5 is [ 5 ], [ 10, 5 ]
อินพุต
arr[] = {10, 21, 7, 8}, GCD[] = {2, 7, 5} ผลลัพธ์
Count of number of subsets of a set with GCD equal to a given number are: 1 2 0
คำอธิบาย
The subsets with GCD equal to 2 is [ 10, 8 ]. Subsets with GCD equal to 7 is [ 7 ], [ 21,7 ] There are no subsets with GCD equal to 5.
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในแนวทางนี้ เราจะสร้าง unordered_map
-
รับสองอาร์เรย์สำหรับ arr[] และ GCD[]
-
ฟังก์ชัน subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) รับทั้งอาร์เรย์และความยาว และส่งคืนค่าจำนวนชุดย่อยของชุดที่มี GCD เท่ากับจำนวนที่กำหนด
-
ฟังก์ชัน subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD) รับทั้งอาร์เรย์และความยาว และส่งคืนค่าจำนวนชุดย่อยของชุดที่มี GCD เท่ากับจำนวนที่กำหนด
-
นับเริ่มต้นเป็น 0
-
Traverse arr[] ใช้ for loop และค้นหาจำนวนการอัปเดตเป็นค่าสูงสุดและอัปเดต um_1 ด้วยความถี่โดยใช้ um_1[arr[i]]++
-
ใช้ for loop จาก i=count ถึง i>=1 ให้นำผลรวมเป็นผลรวมของความถี่ของทวีคูณของ i และ temp=0 เป็นจำนวนเซตย่อยที่มี gcd มากกว่า i แต่ไม่เท่ากับ i
-
ข้ามอีกครั้งจาก j=2 ถึง j*i<=count เพิ่ม um_1[j*i] ไปที่ยอดรวม และเพิ่ม um_2[j*i] ไปที่ temp.
-
หลังจากสิ้นสุดทั้งสอง for loops ให้ตั้งค่า um_2[i] =(1<
-
พิมพ์ um_2[GCD[i]] สำหรับอาร์เรย์ผลลัพธ์ที่มีการนับชุดย่อยโดยให้ GCD
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
void subset_GCD(int arr[], int size_arr, int GCD[], int size_GCD){
unordered_map<int, int> um_1, um_2;
int count = 0;
for (int i=0; i<size_arr; i++){
count = max(count, arr[i]);
um_1[arr[i]]++;
}
for (int i = count; i >=1; i−−){
int temp = 0;
int total = um_1[i];
for (int j = 2; j*i <= count; j++){
total += um_1[j*i];
temp += um_2[j*i];
}
um_2[i] = (1<<total) − 1 − temp;
}
cout<<"Count of number of subsets of a set with GCD equal to a given number are: ";
for (int i=0; i<size_GCD ; i++){
cout<<um_2[GCD[i]]<<" ";
}
}
int main(){
int GCD[] = {2, 3};
int arr[] = {9, 6, 2};
int size_arr = sizeof(arr)/sizeof(arr[0]);
int size_GCD = sizeof(GCD)/sizeof(GCD[0]);
subset_GCD(arr, size_arr, GCD, size_GCD);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of number of subsets of a set with GCD equal to a given number are: 2 1
