Count subsets consisting of each element as a factor of the next element in that subset | C ++ program for 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
#include <bits/stdc++.h> NEW_LINE #define mod  1000000007 NEW_LINE using namespace std ; void countSets ( int * arr , int n ) { int cnt = 0 ; int maxE = -1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( maxE < arr [ i ] ) maxE = arr [ i ] ; } int * sieve = new int [ maxE + 1 ] ; for ( int i = 0 ; i <= maxE ; i ++ ) sieve [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) sieve [ arr [ i ] ] = 1 ; for ( int i = 1 ; i <= maxE ; i ++ ) { if ( sieve [ i ] != 0 ) { for ( int j = i * 2 ; j <= maxE ; j += i ) { if ( sieve [ j ] != 0 ) sieve [ j ] = ( sieve [ j ] + sieve [ i ] ) % mod ; } } } for ( int i = 0 ; i <= maxE ; i ++ ) cnt = ( cnt % mod + sieve [ i ] % mod ) % mod ; delete [ ] sieve ; cout << cnt % mod ; } int main ( ) { int arr [ ] = { 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; countSets ( arr , N ) ; return 0 ; }