human
Write me a code to count number of subsets of a set with GCD equal to a given number and the other steps required given the following:
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"
Solution in Python:
assistant
#Here is code to count number of subsets of a set with GCD equal to a given number and the other steps required.
 def countSubsets ( arr , n , gcd , m ) :
	freq = dict ( )
	subsets = dict ( )
	arrMax = 0
	for i in range ( n ) :
		arrMax = max ( arrMax , arr [ i ] )
		if arr [ i ] not in freq :
			freq [ arr [ i ] ] = 1
		else :
			freq [ arr [ i ] ] += 1
	for i in range ( arrMax , 0 , - 1 ) :
		sub = 0
		add = 0
		if i in freq :
			add = freq [ i ]
		j = 2
		while j * i <= arrMax :
			if j * i in freq :
				add += freq [ j * i ]
			sub += subsets [ j * i ]
			j += 1
		subsets [ i ] = ( 1 << add ) - 1 - sub
	for i in range ( m ) :
		print ( " Number ▁ of ▁ subsets ▁ with ▁ gcd ▁ % d ▁ is ▁ % d " % ( gcd [ i ] , subsets [ gcd [ i ] ] ) )
if __name__ == " _ _ main _ _ " :
	gcd = [ 2 , 3 ]
	arr = [ 9 , 6 , 2 ]
	n = len ( arr )
	m = len ( gcd )
	countSubsets ( arr , n , gcd , m )