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 Math . Pow ( 2 , add ) - 1 - sub ; Driver code
using System ; using System . Collections . Generic ; class GFG { static void ccountSubsets ( int [ ] arr , int n , int [ ] gcd , int m ) { Dictionary < int , int > freq = new Dictionary < int , int > ( ) ; Dictionary < int , int > subsets = new Dictionary < int , int > ( ) ; int arrMax = 0 ; for ( int i = 0 ; i < n ; i ++ ) { arrMax = Math . Max ( arrMax , arr [ i ] ) ; if ( freq . ContainsKey ( arr [ i ] ) ) { freq . Add ( arr [ i ] , freq [ arr [ i ] ] + 1 ) ; } else { freq . Add ( arr [ i ] , 1 ) ; } } for ( int i = arrMax ; i >= 1 ; i -- ) { int sub = 0 ; int add = 0 ; if ( freq . ContainsKey ( i ) ) add = freq [ i ] ; for ( int j = 2 ; j * i <= arrMax ; j ++ ) { if ( freq . ContainsKey ( i * j ) ) add += freq [ j * i ] ; sub += subsets [ j * i ] ; } subsets . Add ( i , ( 1 << add ) - 1 - sub ) ; } for ( int i = 0 ; i < m ; i ++ ) Console . Write ( " Number ▁ of ▁ subsets ▁ with ▁ gcd ▁ " + gcd [ i ] + " ▁ is ▁ " + subsets [ gcd [ i ] ] + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { int [ ] gcd = { 2 , 3 } ; int [ ] arr = { 9 , 6 , 2 } ; int n = arr . Length ; int m = gcd . Length ; ccountSubsets ( arr , n , gcd , m ) ; } }