Find the length of the Largest subset such that all elements are Pairwise Coprime | Dynamic programming table ; Function to obtain the mask for any integer ; List of prime numbers till 50 ; Iterate through all prime numbers to obtain the mask ; Set this prime 's bit ON in the mask ; Return the mask value ; Function to count the number of ways ; Check if subproblem has been solved ; Excluding current element in the subset ; Check if there are no common prime factors then only this element can be included ; Calculate the new mask if this element is included ; Store and return the answer ; Function to find the count of subarray with all digits unique ; Initializing dp ; Driver code
var dp = Array . from ( Array ( 5000 ) , ( ) => Array ( ( 1 << 10 ) + 5 ) ) ; function getmask ( val ) { var mask = 0 ; var prime = [ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 ] ; for ( var i = 0 ; i < 15 ; i ++ ) { if ( val % prime [ i ] == 0 ) { mask = mask | ( 1 << i ) ; } } return mask ; } function calculate ( pos , mask , a , n ) { if ( pos == n || mask == ( 1 << n - 1 ) ) return 0 ; if ( dp [ pos ] [ mask ] != - 1 ) return dp [ pos ] [ mask ] ; var size = 0 ; size = Math . max ( size , calculate ( pos + 1 , mask , a , n ) ) ; if ( ( getmask ( a [ pos ] ) & mask ) == 0 ) { var new_mask = ( mask | ( getmask ( a [ pos ] ) ) ) ; size = Math . max ( size , 1 + calculate ( pos + 1 , new_mask , a , n ) ) ; } return dp [ pos ] [ mask ] = size ; } function largestSubset ( a , n ) { dp = Array . from ( Array ( 5000 ) , ( ) => Array ( ( 1 << 10 ) + 5 ) . fill ( - 1 ) ) ; return calculate ( 0 , 0 , a , n ) ; } var A = [ 2 , 3 , 13 , 5 , 14 , 6 , 7 , 11 ] ; var N = A . length ; document . write ( largestSubset ( A , N ) ) ;