Count subsets consisting of each element as a factor of the next element in that subset | 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 ; Prthe result ; Driver Code ; Function Call
def countSets ( arr , n ) : NEW_LINE INDENT cnt = 0 NEW_LINE maxE = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( maxE < arr [ i ] ) : NEW_LINE INDENT maxE = arr [ i ] NEW_LINE DEDENT DEDENT sieve = [ 0 ] * ( maxE + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT sieve [ arr [ i ] ] = 1 NEW_LINE DEDENT for i in range ( 1 , maxE + 1 ) : NEW_LINE INDENT if ( sieve [ i ] != 0 ) : NEW_LINE INDENT for j in range ( i * 2 , maxE + 1 , i ) : NEW_LINE INDENT if ( sieve [ j ] != 0 ) : NEW_LINE INDENT sieve [ j ] = ( sieve [ j ] + sieve [ i ] ) % 1000000007 NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( maxE + 1 ) : NEW_LINE INDENT cnt = ( cnt % 1000000007 + sieve [ i ] % 1000000007 ) % 1000000007 NEW_LINE DEDENT print ( cnt % 1000000007 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 ] NEW_LINE N = len ( arr ) NEW_LINE countSets ( arr , N ) NEW_LINE DEDENT