Count subsets consisting of each element as a factor of the next element in that subset
Given an array arr[] of size N, the task is to find the number of non-empty subsets present in the array such that every element( except the last) in the subset is a factor of the next adjacent element present in that subset. The elements in a subset can be rearranged, therefore, if any rearrangement of a subset satisfies the condition, then that subset will be counted in. However, this subset should be counted in only once.
Examples:
Input: arr[] = {2, 3, 6, 8}
Output: 7
Explanation:
The required subsets are: {2}, {3}, {6}, {8}, {2, 6}, {8, 2}, {3, 6}.
Since subsets {2}, {3}, {6}, {8} contains a single number, they are included in the answer.
In the subset {2, 6}, 2 is a factor of 6.
In the subset {3, 6}, 3 is a factor of 6.
{8, 2} when rearranged into {2, 8}, satisfies the required condition.Input: arr[] = {16, 18, 6, 7, 2, 19, 20, 9}
Output: 15
Naive Approach: The simplest idea is to generate all possible subsets of the array and print the count of those subsets whose adjacent element (arr[i], arr[i + 1]), arr[i] is a factor of arr[i + 1].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #define mod 1000000007 using namespace std; // Function to calculate each subset // for the array using bit masking set< int > getSubset( int n, int * arr, int mask) { // Stores the unique elements // of the array arr[] set< int > subset; // Traverse the array for ( int i = 0; i < n; i++) { // Get the ith bit of the mask int b = (mask & (1 << i)); // ith bit of mask is set then // include the corresponding // element in subset if (b != 0) { subset.insert(arr[i]); } } return subset; } // Function to count the subsets // that satisfy the given condition int countSets( int n, set< int >* power_set) { // Store the count of subsets int count = 0; // Iterate through all the sets // in the power set for ( int i = 1; i < (1 << n); i++) { // Initially, set flag as true bool flag = true ; int N = power_set[i].size(); // Convert the current subset // into an array int * temp = new int [N]; auto it = power_set[i].begin(); for ( int j = 0; it != power_set[i].end(); j++, it++) { temp[j] = *it; } // Check for any index, i, // a[i] is a factor of a[i+1] for ( int k1 = 1, k0 = 0; k1 < N;) { if (temp[k1] % temp[k0] != 0) { flag = false ; break ; } if (k0 > 0) k0--; else { k1++; k0 = k1 - 1; } } // If flag is still set, then // update the count if (flag) count = 1LL * (count + 1) % mod; delete [] temp; } // Return the final count return count; } // Function to generate power set of // the given array arr[] void generatePowerSet( int arr[], int n) { // Declare power set of size 2^n set< int >* power_set = new set< int >[1 << n]; // Represent each subset using // some mask int mask = 0; for ( int i = 0; i < (1 << n); i++) { power_set[i] = getSubset(n, arr, mask); mask++; } // Find the required number of // subsets cout << countSets(n, power_set) % mod; delete [] power_set; } // Driver Code int main() { int arr[] = { 16, 18, 6, 7, 2, 19, 20, 9 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call generatePowerSet(arr, N); return 0; } |
Java
import java.util.*; class MainClass { static int mod = 1000000007 ; // Function to calculate each subset // for the array using bit masking static HashSet<Integer> GetSubset( int n, int [] arr, int mask) { // Stores the unique elements // of the array arr[] HashSet<Integer> subset = new HashSet<Integer>(); // Traverse the array for ( int i = 0 ; i < n; i++) { // Get the ith bit of the mask int b = mask & ( 1 << i); // ith bit of mask is set then // include the corresponding // element in subset if (b != 0 ) { subset.add(arr[i]); } } return subset; } // Function to count the subsets // that satisfy the given condition static int CountSets( int n, HashSet<Integer>[] powerSet) { // Store the count of subsets int count = 0 ; // Iterate through all the sets // in the power set for ( int i = 1 ; i < ( 1 << n); i++) { // Initially, set flag as true boolean flag = true ; int N = powerSet[i].size(); // Convert the current subset // into an array Integer[] temp = powerSet[i].toArray( new Integer[N]); Arrays.sort(temp, (a, b) -> a - b); // Check for any index, i, // a[i] is a factor of a[i+1] int k1 = 1 ; int k0 = 0 ; for (k1 = 1 ; k1 < N;) { if (temp[k1] % temp[k0] != 0 ) { flag = false ; break ; } if (k0 > 0 ) k0--; else { k1++; k0 = k1 - 1 ; } } // If flag is still set, then // update the count if (flag == true ) count = (count + 1 ) % mod; } // Return the final count return count; } // Function to generate power set of // the given array arr[] static void GeneratePowerSet( int [] arr, int n) { // Declare power set of size 2^n HashSet<Integer>[] powerSet = new HashSet[ 1 << n]; for (var i = 0 ; i < ( 1 << n); i++) powerSet[i] = new HashSet<Integer>(); // Represent each subset using // some mask var mask = 0 ; for (var i = 0 ; i < ( 1 << n); i++) { powerSet[i] = GetSubset(n, arr, mask); mask++; } // Find the required number of // subsets System.out.println(CountSets(n, powerSet) % mod); } // Driver Code public static void main(String[] args) { int [] arr = { 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 }; int N = arr.length; // Function Call GeneratePowerSet(arr, N); } } // This code is contributed by phasing17. |
Python3
mod = 1000000007 # Function to calculate each subset # for the array using bit masking def get_subset(n, arr, mask): # Stores the unique elements # of the array arr[] subset = set () # Traverse the array for i in range (n): # Get the ith bit of the mask b = mask & ( 1 << i) # ith bit of mask is set then # include the corresponding # element in subset if b ! = 0 : subset.add(arr[i]) return subset # Function to count the subsets # that satisfy the given condition def count_sets(n, power_set): # Store the count of subsets count = 0 # Iterate through all the sets # in the power set for i in range ( 1 , 1 << n): # Initially, set flag as true flag = True N = len (power_set[i]) # Convert the current subset # into a list temp = list (power_set[i]) temp.sort(key = lambda x: x) # Check for any index, i, # a[i] is a factor of a[i+1] k1 = 1 k0 = 0 while k1 < N: if temp[k1] % temp[k0] ! = 0 : flag = False break if k0 > 0 : k0 - = 1 else : k1 + = 1 k0 = k1 - 1 # If flag is still set, then # update the count if flag: count = (count + 1 ) % mod # Return the final count return count # Function to generate power set of # the given array arr[] def generate_power_set(arr, n): # Declare power set of size 2^n power_set = [ set () for _ in range ( 1 << n)] # Represent each subset using # some mask mask = 0 for i in range ( 1 << n): power_set[i] = get_subset(n, arr, mask) mask + = 1 # Find the required number of # subsets print (count_sets(n, power_set) % mod) # Driver Code arr = [ 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 ] N = len (arr) # Function Call generate_power_set(arr, N) # This code is contributed by phasing17 |
C#
using System; using System.Collections.Generic; using System.Linq; class MainClass { static int mod = 1000000007; // Function to calculate each subset // for the array using bit masking static HashSet< int > GetSubset( int n, int [] arr, int mask) { // Stores the unique elements // of the array arr[] HashSet< int > subset = new HashSet< int >(); // Traverse the array for ( int i = 0; i < n; i++) { // Get the ith bit of the mask int b = mask & (1 << i); // ith bit of mask is set then // include the corresponding // element in subset if (b != 0) { subset.Add(arr[i]); } } return subset; } // Function to count the subsets // that satisfy the given condition static int CountSets( int n, HashSet< int >[] powerSet) { // Store the count of subsets int count = 0; // Iterate through all the sets // in the power set for ( int i = 1; i < (1 << n); i++) { // Initially, set flag as true bool flag = true ; int N = powerSet[i].Count; // Convert the current subset // into an array int [] temp = powerSet[i].ToArray(); Array.Sort(temp, (a, b) => a - b); // Check for any index, i, // a[i] is a factor of a[i+1] int k1 = 1; int k0 = 0; for (k1 = 1; k1 < N;) { if (temp[k1] % temp[k0] != 0) { flag = false ; break ; } if (k0 > 0) k0--; else { k1++; k0 = k1 - 1; } } // If flag is still set, then // update the count if (flag == true ) count = (count + 1) % mod; } // Return the final count return count; } // Function to generate power set of // the given array arr[] static void GeneratePowerSet( int [] arr, int n) { // Declare power set of size 2^n HashSet< int >[] powerSet = new HashSet< int >[1 << n]; for ( var i = 0; i < (1 << n); i++) powerSet[i] = new HashSet< int >(); // Represent each subset using // some mask var mask = 0; for ( var i = 0; i < (1 << n); i++) { powerSet[i] = GetSubset(n, arr, mask); mask++; } // Find the required number of // subsets Console.WriteLine(CountSets(n, powerSet) % mod); } // Driver Code public static void Main( string [] args) { int [] arr = { 16, 18, 6, 7, 2, 19, 20, 9 }; int N = arr.Length; // Function Call GeneratePowerSet(arr, N); } } // This code is contributed by phasing17. |
Javascript
// JavaScript program for the above approach let mod = 1000000007 // Function to calculate each subset // for the array using bit masking function getSubset(n, arr, mask) { // Stores the unique elements // of the array arr[] let subset = new Set(); // Traverse the array for ( var i = 0; i < n; i++) { // Get the ith bit of the mask var b = (mask & (1 << i)); // ith bit of mask is set then // include the corresponding // element in subset if (b != 0) { subset.add(arr[i]); } } return subset; } // Function to count the subsets // that satisfy the given condition function countSets( n, power_set) { // Store the count of subsets var count = 0; // Iterate through all the sets // in the power set for ( var i = 1; i < (1 << n); i++) { // Initially, set flag as true var flag = true ; var N = power_set[i].size; // Convert the current subset // into an array let temp = Array.from(power_set[i]) temp.sort( function (a, b) { return a - b; }) // Check for any index, i, // a[i] is a factor of a[i+1] var k1 = 1; var k0 = 0; for (k1 = 1; k1 < N;) { if (temp[k1] % temp[k0] != 0) { flag = false ; break ; } if (k0 > 0) k0--; else { k1++; k0 = k1 - 1; } } // If flag is still set, then // update the count if (flag == true ) count = (count + 1) % mod; } // Return the final count return count; } // Function to generate power set of // the given array arr[] function generatePowerSet(arr, n) { // Declare power set of size 2^n let power_set = new Array(1 << n) for ( var i = 0; i < (1 << n); i++) power_set[i] = new Set() // Represent each subset using // some mask var mask = 0; for ( var i = 0; i < (1 << n); i++) { power_set[i] = getSubset(n, arr, mask); mask++; } // Find the required number of // subsets console.log (countSets(n, power_set) % mod); } // Driver Code var arr = [ 16, 18, 6, 7, 2, 19, 20, 9 ]; var N = arr.length; // Function Call generatePowerSet(arr, N); // This code is contributed by phasing17. |
15
Time Complexity: O(N*2N)
Auxiliary Space: O(1)
HashMap-based Approach: To optimize the above approach, the idea is to use a hashmap and an array dp[] to store the array elements in a sorted manner and keeps a count of the subsets as well. For index i, dp[arr[i]] will store the number of all subsets satisfying the given conditions ending at index i. Follow the steps below to solve the problem:
- Initialize cnt as 0 to store the number of required subsets.
- Initialize a hashmap, dp and mark dp[arr[i]] with 1 for every i over the range [0, N – 1].
- Traverse the array dp[] using the variable i and nested traverse from i to begin using iterator j and if i is not equal to j, and element at j is a factor of the element at i, then update dp[i] += dp[j].
- Again, traverse the map and update cnt as cnt += dp[i].
- After the above steps, print the value of cnt as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #define mod 1000000007 using namespace std; // Function that counts subsets whose // every element is divisible by the // previous adjacent element void countSets( int * arr, int n) { // Declare a map map< int , int > dp; // Initialise dp[arr[i]] with 1 for ( int i = 0; i < n; i++) dp[arr[i]] = 1; // Traverse the map till end map< int , int >::iterator i = dp.begin(); for (; i != dp.end(); i++) { // Traverse the map from i to // begin using iterator j map< int , int >::iterator j = i; for (; j != dp.begin(); j--) { if (i == j) continue ; // Check if condition is true if (i->first % j->first == 0) { // If factor found, append // i at to all subsets i->second = (i->second % mod + j->second % mod) % mod; } } // Check for the first element // of the map if (i != j && i->first % j->first == 0) { i->second = (i->second % mod + j->second % mod) % mod; } } // Store count of required subsets int cnt = 0; // Traverse the map for (i = dp.begin(); i != dp.end(); i++) // Update the cnt variable cnt = (cnt % mod + i->second % mod) % mod; // Print the result cout << cnt % mod; } // Driver Code int main() { int arr[] = { 16, 18, 6, 7, 2, 19, 20, 9 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call countSets(arr, N); return 0; } |
Java
import java.util.*; import java.util.TreeMap; public class Main { // Function that counts subsets whose // every element is divisible by the // previous adjacent element static void countSets( int [] arr) { // Declare a map TreeMap<Integer, Integer> dp = new TreeMap<>(); // Initialise dp[arr[i]] with 1 for ( int i = 0 ; i < arr.length; i++) dp.put(arr[i], 1 ); for (Map.Entry<Integer, Integer> i : dp.entrySet()) { for (Map.Entry<Integer, Integer> j : dp.headMap(i.getKey()).entrySet()) { if (i.getKey() == j.getKey()) continue ; // Check if condition is true if (i.getKey() % j.getKey() == 0 ) { // If factor found, append // i at to all subsets i.setValue( (i.getValue() + j.getValue())); } } } // Store count of required subsets int cnt = 0 ; // Traverse the map for (Map.Entry<Integer, Integer> i : dp.entrySet()) // Update the cnt variable cnt += i.getValue(); // Print the result System.out.println(cnt); } //Driver code public static void main(String[] args) { int [] arr = { 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 }; // Function Call countSets(arr); } } // This code is contributed by ritaagarwal. |
Python3
# Python3 code to implement the approach MOD = 1000000007 def countSets(arr, n): # Declare a dictionary dp = {} # Initialise dp[arr[i]] with 1 for i in range (n): dp[arr[i]] = 1 # Traverse the dictionary till end for i in sorted (dp): # Traverse the dictionary from i to # begin using j for j in reversed ( list (dp.keys())): if i = = j: continue # Check if condition is true if i % j = = 0 : # If factor found, append # i at to all subsets dp[i] = (dp[i] % MOD + dp[j] % MOD) % MOD # Check for the first element # of the map if i ! = list (dp.keys())[ 0 ] and i % list (dp.keys())[ 0 ] = = 0 : dp[i] = (dp[i] % MOD + dp[ list (dp.keys())[ 0 ]] % MOD) % MOD # Store count of required subsets cnt = 0 # Traverse the dictionary for i in dp: # Update the cnt variable cnt = (cnt % MOD + dp[i] % MOD) % MOD # Print the result print (cnt % MOD) # Driver Code arr = [ 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 ] N = len (arr # Function Call countSets(arr, N) # This code is contributed by phasing17 |
C#
// C# code to implement the approach using System; using System.Collections.Generic; using System.Linq; class GFG { // Function that counts subsets whose every element is // divisible by the previous adjacent element static void CountSets( int [] arr) { // Declare a map SortedDictionary< int , int > dp = new SortedDictionary< int , int >(); // Initialise dp[arr[i]] with 1 for ( int i = 0; i < arr.Length; i++) dp.Add(arr[i], 1); for ( int i = 0; i < dp.Count; i++) { KeyValuePair< int , int > outer = dp.ElementAt(i); for ( int j = 0; j < i; j++) { KeyValuePair< int , int > inner = dp.ElementAt(j); if (outer.Key == inner.Key) continue ; if (outer.Key % inner.Key == 0) { dp[outer.Key] = dp[outer.Key] + dp[inner.Key]; } } } // Store count of required subsets int cnt = 0; // Traverse the map foreach (KeyValuePair< int , int > i in dp) // Update the cnt variable cnt += i.Value; // Print the result Console.WriteLine(cnt); } // Driver code public static void Main( string [] args) { int [] arr = { 16, 18, 6, 7, 2, 19, 20, 9 }; // Function Call CountSets(arr); } } // This code is contributed by phasing17 |
Javascript
let dp = new Map(); // Function that counts subsets whose // every element is divisible by the // previous adjacent element function countSets(arr) { // Initialise dp[arr[i]] with 1 for (let i = 0; i < arr.length; i++) { dp.set(arr[i], 1); } for (let [iKey, iValue] of dp) { for (let [jKey, jValue] of Array.from(dp.entries()).slice(0, dp.size - dp.get(iKey))) { if (iKey == jKey) { continue ; } // Check if condition is true if (iKey % jKey == 0) { // If factor found, append // i at to all subsets dp.set(iKey, (iValue + jValue)); } } } // Store count of required subsets let cnt = 0; // Traverse the map for (let [key, value] of dp) { // Update the cnt variable cnt += value; } // Print the result console.log(cnt); } //Driver code let arr = [16, 18, 6, 7, 2, 19, 20, 9]; // Function Call countSets(arr); |
15
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use the similar concept to Sieve of Eratosthenes. Follow the steps below to solve the problem:
- Create an array sieve[] of size greatest element in the array(say maxE), arr[] and initialize with 0s.
- Set sieve[i] = 1 where i is the elements of the array.
- Traverse the array sieve[] over the range [1, maxE]using the variable i and if the value of sieve[i] is positive then add the sieve[i] to all the multiples of i(say j) if the sieve[j] is positive.
- After completing the above steps, print the sum of the elements of the array sieve[] as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #define mod 1000000007 using namespace std; // Function to find number of subsets // satisfying the given condition void countSets( int * arr, int n) { // Stores number of required sets int cnt = 0; // Stores maximum element of arr[] // that defines the size of sieve int maxE = -1; // Iterate through the arr[] for ( int i = 0; i < n; i++) { // If current element > maxE, // then update maxE if (maxE < arr[i]) maxE = arr[i]; } // Declare an array sieve of size N + 1 int * sieve = new int [maxE + 1]; // Initialize with all 0s for ( int i = 0; i <= maxE; i++) sieve[i] = 0; // Mark all elements corresponding in // the array, by one as there will // always exists a singleton set for ( int i = 0; i < n; i++) sieve[arr[i]] = 1; // Iterate from range [1, N] for ( int i = 1; i <= maxE; i++) { // If element is present in array if (sieve[i] != 0) { // Traverse through all its // multiples <= n for ( int j = i * 2; j <= maxE; j += i) { // Update them if they // are present in array if (sieve[j] != 0) sieve[j] = (sieve[j] + sieve[i]) % mod; } } } // Iterate from the range [1, N] for ( int i = 0; i <= maxE; i++) // Update the value of cnt cnt = (cnt % mod + sieve[i] % mod) % mod; delete [] sieve; // Print the result cout << cnt % mod; } // Driver Code int main() { int arr[] = { 16, 18, 6, 7, 2, 19, 20, 9 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call countSets(arr, N); return 0; } |
Java
// Java Program to implement // the above approach import java.io.*; import java.util.*; class GFG { static int mod = 1000000007 ; // Function to find number of subsets // satisfying the given condition static void countSets( int arr[], int n) { // Stores number of required sets int cnt = 0 ; // Stores maximum element of arr[] // that defines the size of sieve int maxE = - 1 ; // Iterate through the arr[] for ( int i = 0 ; i < n; i++) { // If current element > maxE, // then update maxE if (maxE < arr[i]) maxE = arr[i]; } // Declare an array sieve of size N + 1 int sieve[] = new int [maxE + 1 ]; // Mark all elements corresponding in // the array, by one as there will // always exists a singleton set for ( int i = 0 ; i < n; i++) sieve[arr[i]] = 1 ; // Iterate from range [1, N] for ( int i = 1 ; i <= maxE; i++) { // If element is present in array if (sieve[i] != 0 ) { // Traverse through all its // multiples <= n for ( int j = i * 2 ; j <= maxE; j += i) { // Update them if they // are present in array if (sieve[j] != 0 ) sieve[j] = (sieve[j] + sieve[i]) % mod; } } } // Iterate from the range [1, N] for ( int i = 0 ; i <= maxE; i++) // Update the value of cnt cnt = (cnt % mod + sieve[i] % mod) % mod; // Print the result System.out.println(cnt % mod); } // Driver Code public static void main(String[] args) { int arr[] = { 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 }; int N = arr.length; // Function Call countSets(arr, N); } } // This code is contributed by Kingash. |
Python3
#mod 1000000007 # Function to find number of subsets # satisfying the given condition def countSets(arr, n): # Stores number of required sets cnt = 0 # Stores maximum element of arr[] # that defines the size of sieve maxE = - 1 # Iterate through the arr[] for i in range (n): # If current element > maxE, # then update maxE if (maxE < arr[i]): maxE = arr[i] # Declare an array sieve of size N + 1 sieve = [ 0 ] * (maxE + 1 ) # Mark all elements corresponding in # the array, by one as there will # always exists a singleton set for i in range (n): sieve[arr[i]] = 1 # Iterate from range [1, N] for i in range ( 1 , maxE + 1 ): # If element is present in array if (sieve[i] ! = 0 ): # Traverse through all its # multiples <= n for j in range (i * 2 , maxE + 1 , i): # Update them if they # are present in array if (sieve[j] ! = 0 ): sieve[j] = (sieve[j] + sieve[i]) % 1000000007 # Iterate from the range [1, N] for i in range (maxE + 1 ): # Update the value of cnt cnt = (cnt % 1000000007 + sieve[i] % 1000000007 ) % 1000000007 #delete[] sieve # Print the result print (cnt % 1000000007 ) # Driver Code if __name__ = = '__main__' : arr = [ 16 , 18 , 6 , 7 , 2 , 19 , 20 , 9 ] N = len (arr) # Function Call countSets(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# Program to implement // the above approach using System; class GFG { static int mod = 1000000007; // Function to find number of subsets // satisfying the given condition static void countSets( int [] arr, int n) { // Stores number of required sets int cnt = 0; // Stores maximum element of arr[] // that defines the size of sieve int maxE = -1; // Iterate through the arr[] for ( int i = 0; i < n; i++) { // If current element > maxE, // then update maxE if (maxE < arr[i]) maxE = arr[i]; } // Declare an array sieve of size N + 1 int [] sieve = new int [maxE + 1]; // Mark all elements corresponding in // the array, by one as there will // always exists a singleton set for ( int i = 0; i < n; i++) sieve[arr[i]] = 1; // Iterate from range [1, N] for ( int i = 1; i <= maxE; i++) { // If element is present in array if (sieve[i] != 0) { // Traverse through all its // multiples <= n for ( int j = i * 2; j <= maxE; j += i) { // Update them if they // are present in array if (sieve[j] != 0) sieve[j] = (sieve[j] + sieve[i]) % mod; } } } // Iterate from the range [1, N] for ( int i = 0; i <= maxE; i++) // Update the value of cnt cnt = (cnt % mod + sieve[i] % mod) % mod; // Print the result Console.WriteLine(cnt % mod); } // Driver Code public static void Main( string [] args) { int [] arr = { 16, 18, 6, 7, 2, 19, 20, 9 }; int N = arr.Length; // Function Call countSets(arr, N); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach let mod = 1000000007; // Function to find number of subsets // satisfying the given condition function countSets(arr,n) { // Stores number of required sets let cnt = 0; // Stores maximum element of arr[] // that defines the size of sieve let maxE = -1; // Iterate through the arr[] for (let i = 0; i < n; i++) { // If current element > maxE, // then update maxE if (maxE < arr[i]) maxE = arr[i]; } // Declare an array sieve of size N + 1 let sieve = new Array(maxE + 1); for (let i=0;i<maxE + 1;i++) { sieve[i]=0; } // Mark all elements corresponding in // the array, by one as there will // always exists a singleton set for (let i = 0; i < n; i++) sieve[arr[i]] = 1; // Iterate from range [1, N] for (let i = 1; i <= maxE; i++) { // If element is present in array if (sieve[i] != 0) { // Traverse through all its // multiples <= n for (let j = i * 2; j <= maxE; j += i) { // Update them if they // are present in array if (sieve[j] != 0) sieve[j] = (sieve[j] + sieve[i]) % mod; } } } // Iterate from the range [1, N] for (let i = 0; i <= maxE; i++) // Update the value of cnt cnt = (cnt % mod + sieve[i] % mod) % mod; // Print the result document.write(cnt % mod+ "<br>" ); } // Driver Code let arr=[16, 18, 6, 7, 2, 19, 20, 9 ]; let N = arr.length; // Function Call countSets(arr, N); // This code is contributed by avanitrachhadiya2155 </script> |
15
Time Complexity: O(maxE*log(log (maxE)))
Auxiliary Space: O(maxE)