Largest Divisible Subset

Approach 1: Naive 

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach is to find all the subsets and find the subset with the maximum length that satisfies the given condition. 

To check the condition its important that we sort the array because 

S[i] % S[j] ==0 can only be possible if S[i] >= S[j] and S[i] !=0.

Also if S[i]%S[j]==0, then all elements which divide S[j] also divide S[i]. Hence we can sort the array to check the condition.

So the naive/basic approach could be formulated as follows:

1. Compute all subsets
2. Check if the subset satisfies the condition
3. If it does, then update the answer and find the maximum length subset.   

Now let’s look at the PseudoCode.

PseudoCode

Algorithm

___________________________________________________________________

procedure LargestDivisibleSubset(arr):

1.    subsets ← computeSubsets(arr),  largest_subset ← empty vector

2.    for each subset in subsets(s) do  

3.        if isDivisibleSubset(subset) and subset.size() > largest_subset.size() do

4.          largest _subset ← subset  

5.     end if   

6.  return largest_subset

7. end procedure

___________________________________________________________________

Implementation in C++

//C++ program to solve the problem  Largest Divisible Subset
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> computeSubsets(vector<int> &arr){
    vector<vector<int>> subsets;
    // we know that subsets can be represented using an integer
    // and there are at most 1<<N subsets
    // hence iterating over all integers from 0 to 1<<N
    int N= arr.size();
    for(int i=0; i<(1<<N); ++i){
        vector<int> v; // current subset
        int j = 0; // variable to check if the bit at a position is set in i
        while((1<<j)<=i){    
            if(((1<<j)&i)>0){ // if bit at current position is set in both i and j
                v.push_back(arr[j]); // push it in the current subset
            }
            j++;      // shift to the next bit
        }
        if(v.size()>0)      // if the subset is not empty push it
            subsets.push_back(v); // in the subsets vector
    }
    // return the subsets
    return subsets;
}
// function to check is the subset Divisble 
bool isDivisibleSubset(vector<int> arr){
    sort(arr.begin(), arr.end()); // sort the array 
    for(int i=arr.size()-1;i>=1;--i){ //check if the current element is Divisble by the previous
        if(arr[i]%arr[i-1]!=0){
            return 0;   // return false if the condition does not hold
        }
    }
    return 1; // return true
}
// function that computes the Largest Divisble subset
vector<int> LargestDivisibleSubset(vector<int> &arr){
    vector<vector<int>> Subsets = computeSubsets(arr); // compute Subsets 
    vector<int> largest_subset; // final answer to be returned
    for(vector<int> subset : Subsets){ // iterate over each subset 
        // check the condition
        if(isDivisibleSubset(subset) and largest_subset.size() < subset.size()){
            largest_subset = subset; // update the result
        }
    }
    return largest_subset;  // return the answer
}
int main() {
    vector<int> arr{1, 2, 4, 8}; // vector
    vector<int> LargestSubset = LargestDivisibleSubset(arr); // compute the result
    cout<<"The LargestDivisibleSubset is: "; // print it
    for(int i:LargestSubset){
        cout<<i<<" ";
    }
    return 0;
}

 

Output

The LargestDivisibleSubset is: 1 2 4 8 

Complexity Analysis

Time Complexity: O(NlogN*2^N), where N is the size of the array 

This is because we sort each subset, and there are 2^N subsets

Space complexity: O(N*2^N), There are 2^N subsets, and each takes O(N) memory.  

The above algorithm works in exponential time, which is good but not an efficient algorithm. This gives us the motivation to improve our algorithm.

So let’s think about an efficient approach to solve the problem.

Approach 2: Efficient 

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing. The redundancy in our code is that we check for every subset of the array if the condition is satisfied. We can make some observations that we can infer to get rid of the extra redundant computation.

As we discussed in the previous approach, we will sort the array, which will help us check if a subset is divisible. Is there anything else that sorting would help us find?

We noticed that if S[i] % S[j] == 0 then all Sk’s in S that divide S[j] would also divide S[i]. So using this, we can store the results and find the length of the subset which satisfies the condition. We see Dynamic programming popping up here!!! (Why?) Since our results depend on the previously computed results.

Let’s define dp[i]  = length of the largest divisible subset containing i^th index. 

So if S[j] % S[i] == 0, dp[j] = max(dp[j], dp[i]+1) for all i 𝞊 [0..j] and maximum of dp[i]’s would find us the length of largest divisible subset.

 

Correctness of the Recurrence(intuition)

Say i^th element is part of a subset with length dp[i], and we need to find dp[j], so j^th element can either be a part of the subset containing i^th element or not. Instead, it can possibly be a part of any subset containing any of the previous elements. Hence, we take dp[j] = max(dp[j], dp[i]+1) for all i 𝞊 [0..j].

Now we have found the length of the largest divisible subset, but we didn’t find the largest divisible subset.

We can maintain another vector/array that stores the previous index, which should be included in the optimal subset. 

Let’s look at the Code.

Implementation in C++

//C++ program to solve the problem  Largest Divisible Subset
#include <bits/stdc++.h>
using namespace std;
vector<int> largestDivisibleSubset(vector<int>& nums) {
        // sort the array 
        sort(nums.begin(), nums.end());
        // the dp array to store the length of largest divisible including the ith element
        vector<int> dp(nums.size(), 0);
        // prev vector to store the previous element index which is in the optimal subset
        vector<int> prev(nums.size(), 0);
        // answer to return and index with maximum subset length
        int ans = 0, idx = 0;
        for(int i=0;i<nums.size();++i) 
            prev[i] = i; // initialise the prev vecctor 
        for(int i=0;i<nums.size();++i){ // iterate over the nums array
            dp[i] = max(1, dp[i]); // initially the current element will be present in the subset of size 1
            for(int j=i-1;j>=0;--j){ // take max using the previous elements to put the current element in the maximum size subset
                if(nums[i]%nums[j]==0) // check if the condition satisfies
                    if(dp[i]<dp[j]+1){ // maximise the dp[i] value
                        dp[i] = dp[j]+1; // update dp[i]
                        prev[i] = j;  // update the prev index
                    }
            }
            if(dp[i]>ans){ // update the answer
                ans = dp[i];
                idx = i; // index from which we can backtrack and get our final optimal subset
            }
        }
        vector<int> res; // output vector
        while(idx!=prev[idx]){ // back track
            res.push_back(nums[idx]);
            idx=  prev[idx];
        }
        res.push_back(nums[idx]); // push the last element in the subset
        return res; // return the result
}
int main() {
    vector<int> arr{1, 2, 4, 8}; // vector
    vector<int> LargestSubset = LargestDivisibleSubset(arr); // compute the result
    cout<<"The LargestDivisibleSubset is: "; // print it
    for(int i:LargestSubset){
        cout<<i<<" ";
    }
    return 0;
}

 

Output

The LargestDivisibleSubset is: 1 2 4 8 

Complexity Analysis

Time Complexity: O(n²)

Since for each index i, we are traversing overall indices j such that 0 < j < i. Since there are n indices, we can write the time complexity is O(n²)

Space complexity: O(n) as we use linear dp and prev vector storing n values.

Hence we reached an efficient solution from an exponential solution. 

Frequently Asked Questions

When is dynamic programming applied? 

Dynamic programming improves the solutions by storing precomputed results when the problem has overlapping subproblems and optimal substructure.

How is the problem LIS solved? 

It’s a very common problem that helps in building the fundamentals of Dynamic programming. LIS is solved using dynamic programming and is optimized using various data structures like segment trees and can also be solved using dp with binary search.

How often are dp and sortings asked in interviews? 

Dp and sortings are favorite topics of the top companies, including Apple, Google, Amazon, etc. It is often asked in interviews, and questions are usually formed using a combination of the 2 topics.

Conclusion

This article taught us how to find the Largest Divisible Subset. We also saw how to approach the problem using a naive approach followed by an efficient solution. We discussed an iterative implementation using examples, pseudocode, and proper code in detail.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out how we can apply dynamic programming and sorting to simplify our task and make fewer comparisons. 

Now, we recommend you practice problem sets based on the concept of finding the Largest Divisible Subset to master your fundamentals. You can get a wide range of questions similar to the problem of finding the Largest Divisible Subset on Coding Ninjas Studio. 

Refer to the most obliging blog on Dynamic programming for your future references→ Roadmap for Dynamic programming.

Check out the Top interview dynamic programming questions to get problems like Longest Common Substring, Friends Pairing, Rod Cutting Problem, Minimum Subset Sum Difference, and Bursting Balloon Problem to read more about these topics in detail.  And if you liked this blog, share it with your friends! 

More Recommended Articles

• Stepping Numbers
• Beautiful Arrangement
• Rotting Oranges
• Alien Dictionary

Suppose you want to learn more about Dynamic Programming data structure and practice some questions that require you to take your basic knowledge of Dynamic Programming a notch higher. In that case, you can visit our Guided Path for Dynamic Programming. If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.