C++ Program: Find the largest divisible subset in an array

This tutorial will discuss a problem where a different array of positive integers is given. We need to find the largest subset such that each pair of larger elements is divided by the smaller element, for example -

Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.

Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1

Methods to find the solution

We will explain both in this tutorial different methods.

Simple method

In the simple method, we can apply recursion to solve this problem. We will get each element and check if it should be included in the subset. Let's say we start with the first element. We will have two choices, either to be included in the subset or not to be included in the first element. Let's include the first element. Then, for the second element to be included in the subset, it should be divisible or divided by the elements in the substring (i.e. the first element). This is how we iterate over the array. Therefore, there will be 2^n possible paths with a time complexity of O(2^n). Let's look at possible solutions to this problem.

Effective method

This problem can be solved by using dynamic programming.

• Sort the array so that the left element is divisible by the correct element. We have to check divisibility once.

• We will take the longest increasing subsequence, our dp[ ] array, to store the largest divisible subset up to the i-th index. We will initialize each index with 1 since each element will divide itself.

• Now we will iterate from the second index and check for each element whether there is a maximum divisible subset ending at the current index. This way, we find the largest subset for each index.

• Now iterate through the array and, for each element, find the divisor with the largest number of divisibles. and changes the divisible count value of the current index to the divisible count of 1 for that element.

Example

C code above method

#include<bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 2, 3, 6};
    int n = sizeof(nums)/sizeof(int);
    // sorting the array to exclude one condition for division.
    sort(nums, nums+n);
    vector <int> prev_res(n, -1);
    // vector to store divisors of all the elements
    vector <int> dp(n, 1);
    int max = 1;
    for (int i=1; i<n; i++){   // Check if there&#39;s a divisor of ith element present at jth index.
        for (int j=0; j<i; j++){
            if (nums[i]%nums[j] == 0){
            // check If adding that increases the number of elements in subsequence.
                if (dp[i] < dp[j] + 1){
                    dp[i] = dp[j]+1;
                    prev_res[i] = j;
                   
                }
            }
        }
   
        // finding index having a maximum number of subsets.
        if(max<dp[i])
            max = dp[i];
    }
    cout << "Largest divisible subset in the array: ";
    // printing the maximum subset
    int k = max;
    while (k >= 0){
        cout << nums[k] << " ";
        k = prev_res[k];
    }
    return 0;
}

Output

Largest divisible subset in the array: 6 2 1

Conclusion

In this tutorial, we discussed a problem: we need to find the largest integrable subset of a given array that is divisible by every pair of integers. We discussed a recursive approach that yields exponential time complexity, so we discussed dynamic programming solutions. We also discussed a C program to solve this problem and we can implement it using programming languages ​​like C, Java, Python etc. We hope you found this tutorial helpful.

The above is the detailed content of C++ Program: Find the largest divisible subset in an array. For more information, please follow other related articles on the PHP Chinese website!