Count of subsets whose product is multiple of unique primes | Function to return gcd of a and b ; Function to check number has distinct prime ; While N has factors of two ; Traversing till sqrt ( N ) ; If N has a factor of i ; While N has a factor of i ; Covering case , N is Prime ; Function to check wheather num can be added to the subset ; Recursive Function to count subset ; Base Case ; If currSubset is empty ; If Unique [ pos ] can be added to the Subset ; Function to count the subsets ; Initialize unique ; Check it is a product of distinct primes ; Count frequency of unique element ; Function Call ; Given Input ; Function Call
function gcd ( a , b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } function checkDistinctPrime ( n ) { let original = n ; let product = 1 ; if ( n % 2 == 0 ) { product *= 2 ; while ( n % 2 == 0 ) { n = parseInt ( n / 2 , 10 ) ; } } for ( let i = 3 ; i < parseInt ( Math . sqrt ( n ) , 10 ) ; i += 2 ) { if ( n % i == 0 ) { product = product * i ; while ( n % i == 0 ) { n = parseInt ( n / i , 10 ) ; } } } if ( n > 2 ) { product = product * n ; } return product == original ; } function check ( pos , subset , unique ) { for ( let num = 0 ; num < subset . length ; num ++ ) { if ( gcd ( subset [ num ] , unique [ pos ] ) != 1 ) { return false ; } } return true ; } function countPrime ( pos , currSubset , unique , frequency ) { if ( pos == unique . length ) { if ( currSubset . length == 0 ) return 0 ; count = 1 ; for ( let element = 0 ; element < currSubset . length ; element ++ ) { count *= frequency [ currSubset [ element ] ] ; } return count ; } if ( check ( pos , currSubset , unique ) ) { return countPrime ( pos + 1 , currSubset , unique , frequency ) + countPrime ( pos + 1 , currSubset + [ unique [ pos ] ] , unique , frequency ) ; } else { return countPrime ( pos + 1 , currSubset , unique , frequency ) ; } } function countSubsets ( arr , N ) { let unique = new Set ( ) ; for ( let element = 0 ; element < arr . length ; element ++ ) { return 5 ; if ( checkDistinctPrime ( element ) ) { unique . add ( element ) ; } } unique = Array . from ( unique ) ; let frequency = new Map ( ) ; for ( let element = 0 ; element < unique . length ; element ++ ) { let freq = 0 ; for ( let i = 0 ; i < unique . length ; i ++ ) { if ( unique [ element ] == unique [ i ] ) { freq ++ ; } } frequency [ element ] = freq ; } let ans = countPrime ( 0 , [ ] , unique , frequency ) ; return ans ; } let arr = [ 2 , 4 , 7 , 10 ] ; let N = arr . length ; let ans = countSubsets ( arr , N ) ; document . write ( ans ) ;