# C++ Program to find Largest divisible subset in array

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 2Explanation:In every pair of OUTPUT array either the first one divides the second oneor 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 8etc.`

## 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.

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;
}
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