Count number of subsets of a set with GCD equal to a given number | Java 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 program
import java . util . * ; class GFG { static void ccountSubsets ( int arr [ ] , int n , int gcd [ ] , int m ) { HashMap < Integer , Integer > freq = new HashMap < Integer , Integer > ( ) ; HashMap < Integer , Integer > subsets = new HashMap < Integer , Integer > ( ) ; int arrMax = 0 ; for ( int i = 0 ; i < n ; i ++ ) { arrMax = Math . max ( arrMax , arr [ i ] ) ; if ( freq . containsKey ( arr [ i ] ) ) { freq . put ( arr [ i ] , freq . get ( arr [ i ] ) + 1 ) ; } else { freq . put ( arr [ i ] , 1 ) ; } } for ( int i = arrMax ; i >= 1 ; i -- ) { int sub = 0 ; int add = 0 ; if ( freq . containsKey ( i ) ) add = freq . get ( i ) ; for ( int j = 2 ; j * i <= arrMax ; j ++ ) { if ( freq . containsKey ( i * j ) ) add += freq . get ( j * i ) ; sub += subsets . get ( j * i ) ; } subsets . put ( i , ( 1 << add ) - 1 - sub ) ; } for ( int i = 0 ; i < m ; i ++ ) System . out . print ( " Number ▁ of ▁ subsets ▁ with ▁ gcd ▁ " + gcd [ i ] + " ▁ is ▁ " + subsets . get ( gcd [ i ] ) + "NEW_LINE"); } 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 ) ; } }