Count subsets consisting of each element as a factor of the next element in that subset

0 0 20 minutes read

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.

Output:

Time Complexity: O(N*2^N)
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);

Output:

Time Complexity: O(N²)
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>

Output:

Time Complexity: O(maxE*log(log (maxE)))
Auxiliary Space: O(maxE)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!