Count number of subsets of a set with GCD equal to a given number | C ++ program to count number of subsets with given GCDs ; n is size of arr [ ] and m is sizeof gcd [ ] ; Map to store frequency of array elements ; Map to store number of subsets with given gcd ; Initialize maximum element . Assumption : all array elements are positive . ; Find maximum element in array and fill frequency map . ; Run a loop from max element to 1 to find subsets with all gcds ; Run a loop for all multiples of i ; Sum the frequencies of every element which is a multiple of i ; Excluding those subsets which have gcd > i but not i i . e . which have gcd as multiple of i in the subset for ex : { 2 , 3 , 4 } considering i = 2 and subset we need to exclude are those having gcd as 4 ; Number of subsets with GCD equal to ' i ' is pow ( 2 , add ) - 1 - sub ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; void ccountSubsets ( int arr [ ] , int n , int gcd [ ] , int m ) { unordered_map < int , int > freq ; unordered_map < int , int > subsets ; int arrMax = 0 ; for ( int i = 0 ; i < n ; i ++ ) { arrMax = max ( arrMax , arr [ i ] ) ; freq [ arr [ i ] ] ++ ; } for ( int i = arrMax ; i >= 1 ; i -- ) { int sub = 0 ; int add = freq [ i ] ; for ( int j = 2 ; j * i <= arrMax ; j ++ ) { add += freq [ j * i ] ; sub += subsets [ j * i ] ; } subsets [ i ] = ( 1 << add ) - 1 - sub ; } for ( int i = 0 ; i < m ; i ++ ) cout << " Number ▁ of ▁ subsets ▁ with ▁ gcd ▁ " << gcd [ i ] << " ▁ is ▁ " << subsets [ gcd [ i ] ] << endl ; } int main ( ) { int gcd [ ] = { 2 , 3 } ; int arr [ ] = { 9 , 6 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int m = sizeof ( gcd ) / sizeof ( gcd [ 0 ] ) ; ccountSubsets ( arr , n , gcd , m ) ; return 0 ; }