Question

You are given a set of N positive integer values. Find the largest subset such that for any two values A and B in the subset, either A divides B or B divides A.
Standard input:
The first line contains a single integer value N. The second line contains N integer values representing the elements of the set. Standard output :
The output should contain a single integer representing the size of the wanted subset.
Example:
5
8 32 12 16 4

4
The clique that contains 4 elements is (8, 32, 16, 4)

Answer 1

Answer:

#include<bits/stdc++.h>  

using namespace std;  

void findLargest(int arr[], int n)  

{  

   int scount=0;

   sort(arr, arr+n);

   vector <int> divCount(n, 1);  

   vector <int> prev(n, -1);  

   int max_ind = 0;  

   for (int i=1; i<n; i++)  

   {  

       for (int j=0; j<i; j++)  

       {  

           if (arr[i]%arr[j] == 0)  

           {  

               if (divCount[i] < divCount[j] + 1)  

               {  

                   divCount[i] = divCount[j]+1;  

                   prev[i] = j;  

               }  

           }  

       }  

       if (divCount[max_ind] < divCount[i])  

           max_ind = i;  

   }  

   int k = max_ind;  

   while (k >= 0)  

   {  

       scount++;

       k = prev[k];  

   }  

   cout<<scount;

}  

 

int main()  

{  

   int arr[100];  

   int n; cin>>n;

   for(int i=0;i<n;i++) cin>>arr[i];

   findLargest(arr, n);  

   return 0;  

}

Explanation: