Count subsets consisting of each element as a factor of the next element in that subset | JavaScript Program to implement the above approach ; Function to find number of subsets satisfying the given condition ; Stores number of required sets ; Stores maximum element of arr [ ] that defines the size of sieve ; Iterate through the arr [ ] ; If current element > maxE , then update maxE ; Declare an array sieve of size N + 1 ; Mark all elements corresponding in the array , by one as there will always exists a singleton set ; Iterate from range [ 1 , N ] ; If element is present in array ; Traverse through all its multiples <= n ; Update them if they are present in array ; Iterate from the range [ 1 , N ] ; Update the value of cnt ; Print the result ; Driver Code ; Function Call
let mod = 1000000007 ; function countSets ( arr , n ) { let cnt = 0 ; let maxE = - 1 ; for ( let i = 0 ; i < n ; i ++ ) { if ( maxE < arr [ i ] ) maxE = arr [ i ] ; } let sieve = new Array ( maxE + 1 ) ; for ( let i = 0 ; i < maxE + 1 ; i ++ ) { sieve [ i ] = 0 ; } for ( let i = 0 ; i < n ; i ++ ) sieve [ arr [ i ] ] = 1 ; for ( let i = 1 ; i <= maxE ; i ++ ) { if ( sieve [ i ] != 0 ) { for ( let j = i * 2 ; j <= maxE ; j += i ) { if ( sieve [ j ] != 0 ) sieve [ j ] = ( sieve [ j ] + sieve [ i ] ) % mod ; } } } for ( let i = 0 ; i <= maxE ; i ++ ) cnt = ( cnt % mod + sieve [ i ] % mod ) % mod ; document . write ( cnt % mod + " " ) ; } let arr = [ 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 ] ; let N = arr . length ; countSets ( arr , N ) ;