C++ Program to find Largest divisible subset in array

By Sakshi Singh

In this tutorial, We will learn how to return largest divisible subset in an array using C++. A subset is said to be divisible if every pair (subset[i], subset[j]) of subset satisfies:

• subset[i] % subset[j] == 0
                  OR
• subset[j] % subset[i] == 0

The naive approach to this problem is by finding all the possible subsets of the array and check for the largest divisible subset. The efficient approach to this problem is discussed below: 

PROBLEM STATEMENT:

Consider an array of distinct positive integers, return the largest divisible subset of the array.

You can return any subset in case of multiple answers.

EXAMPLE:

INPUT, A[] : { 2, 4, 6, 8, 12, 16, 23, 32 }

OUTPUT : 32 16 8 4 2

Explanation:

In every pair of OUTPUT array either the first one divides the second one
or the second one divides the first one.

(2, 4), 2 divides 4
(2, 8), 2 divides 8
(2, 16), 2 divides 16
(2, 32), 2 divides 32
(4, 8), 4 divides 8
etc.

C++ program to return largest divisible subset in array

1. Sort the given array in increasing order so that all the divisor of an element comes before the element.
2. Create an array temp same as the size of the given array to store the count of the divisor of all the elements and initialize all the elements as 1.
3. Traverse every element in the array, for A[j] with the maximum value of temp[j].
4. Update the last index of the longest subset if the current subset is large.
5. Print answer.

Time Complexity: O(n^2)

Implementation of the above algorithm is as follows:

#include<bits/stdc++.h>
using namespace std;
// to find largest divisible subset
void LargestDivSubset(vector<int> A)
{
    int max_index = 0;
    // To store preceding divisor in answer
  vector <int> temp(A.size(), -1);
  // To store count of divisors
  vector <int> count(A.size(), 1);
  //To sort the given array
  sort(A.begin(), A.end());
  for (int i=1; i<A.size(); i++)
  {
    for (int j=0; j<i; j++)
    {
      if (A[i]%A[j] == 0)
      {
        if (count[i] < count[j] + 1)
        {
          count[i] = count[j]+1;
          temp[i] = j;
        }
      }
    }
    // Update last index of largest subset
    if ( count[max_index] < count[i])
      max_index = i;
  }
  //Display the answer
  int k = max_index;
    while (k >= 0)
    {
        cout << A[k] << " ";
        k = temp[k];
    }
}
int main()
{
  vector<int> A = { 2, 4, 6, 8, 12, 16, 23, 32 };
  LargestDivSubset(A);
  return 0;
}

OUTPUT:

32 16 8 4 2

Also, refer

• Subset Sum Problem using DP in C++
• Largest divisible pairs subset