Count number of subsets of a set with GCD equal to a given number | 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 Code
def countSubsets ( arr , n , gcd , m ) : NEW_LINE INDENT freq = dict ( ) NEW_LINE subsets = dict ( ) NEW_LINE arrMax = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT arrMax = max ( arrMax , arr [ i ] ) NEW_LINE if arr [ i ] not in freq : NEW_LINE INDENT freq [ arr [ i ] ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT freq [ arr [ i ] ] += 1 NEW_LINE DEDENT DEDENT for i in range ( arrMax , 0 , - 1 ) : NEW_LINE INDENT sub = 0 NEW_LINE add = 0 NEW_LINE if i in freq : NEW_LINE INDENT add = freq [ i ] NEW_LINE DEDENT j = 2 NEW_LINE while j * i <= arrMax : NEW_LINE INDENT if j * i in freq : NEW_LINE INDENT add += freq [ j * i ] NEW_LINE DEDENT sub += subsets [ j * i ] NEW_LINE j += 1 NEW_LINE DEDENT subsets [ i ] = ( 1 << add ) - 1 - sub NEW_LINE DEDENT for i in range ( m ) : NEW_LINE INDENT print ( " Number ▁ of ▁ subsets ▁ with ▁ gcd ▁ % d ▁ is ▁ % d " % ( gcd [ i ] , subsets [ gcd [ i ] ] ) ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT gcd = [ 2 , 3 ] NEW_LINE arr = [ 9 , 6 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE m = len ( gcd ) NEW_LINE countSubsets ( arr , n , gcd , m ) NEW_LINE DEDENT