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

- Sort the given array in increasing order so that all the divisor of an element comes before the element.
- 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.
- Traverse every element in the array, for A[j] with the maximum value of temp[j].
- Update the last index of the longest subset if the current subset is large.
- 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

## Leave a Reply