# Find the Largest divisor Subset in the Array

• Difficulty Level : Medium
• Last Updated : 05 Jun, 2021

Given an array arr[] of N integers, the task is to find the largest subset of arr[] such that in every pair of numbers from that subset, one number is a divisor of the other.
Examples:

Input: arr[] = {1, 2, 3, 4, 5}
Output: 4 2 1
All possible pairs of the subsequence are:
(4, 2) -> 4 % 2 = 0
(4, 1) -> 4 % 1 = 0
and (2, 1) -> 2 % 1 = 0
Input: arr[] = {1, 3, 4, 9}
Output: 1 3 9

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Approach: Here the task is to find the largest subset where in every pair of numbers, one is divisible by the other i.e. for the sequence a1, a2, a3 … ak where a1 â‰¤ a2 â‰¤ … â‰¤ ak and ai+1 % ai = 0 for every i. This sequence can be found using dynamic programming (similar to longest increasing subsequence).
Below is the implementation of the above approach:

## C++

 `// C++ implementation of the approach``#include ``using` `namespace` `std;` `// Function to find the required subsequence``void` `findSubSeq(``int` `arr[], ``int` `n)``{` `    ``// Sort the array``    ``sort(arr, arr + n);` `    ``// Keep a count of the length of the``    ``// subsequence and the previous element``    ``int` `count[n] = { 1 };``    ``int` `prev[n] = { -1 };` `    ``// Set the initial values``    ``memset``(count, 1, ``sizeof``(count));``    ``memset``(prev, -1, ``sizeof``(prev));` `    ``// Maximum length of the subsequence and``    ``// the last element``    ``int` `max = 0;``    ``int` `maxprev = -1;` `    ``// Run a loop for every element``    ``for` `(``int` `i = 0; i < n; i++) {` `        ``// Check for all the divisors``        ``for` `(``int` `j = i - 1; j >= 0; j--) {` `            ``// If the element is a divisor and the length``            ``// of subsequence will increase by adding``            ``// j as previous element of i``            ``if` `(arr[i] % arr[j] == 0``                ``&& count[j] + 1 > count[i]) {` `                ``// Increase the count``                ``count[i] = count[j] + 1;``                ``prev[i] = j;``            ``}``        ``}` `        ``// Update the max count``        ``if` `(max < count[i]) {``            ``max = count[i];``            ``maxprev = i;``        ``}``    ``}` `    ``// Get the last index of the subsequence``    ``int` `i = maxprev;``    ``while` `(i >= 0) {` `        ``// Print the element``        ``if` `(arr[i] != -1)``            ``cout << arr[i] << ``" "``;` `        ``// Move the index to the previous element``        ``i = prev[i];``    ``}``}` `// Driver code``int` `main()``{``    ``int` `arr[] = { 1, 2, 3, 4, 5 };``    ``int` `n = ``sizeof``(arr) / ``sizeof``(``int``);` `    ``findSubSeq(arr, n);` `    ``return` `0;``}`

## Java

 `// Java implementation of the approach``import` `java.util.*;``class` `GFG``{``    ` `    ``// Function to find the required subsequence``    ``static` `void` `findSubSeq(``int` `arr[], ``int` `n)``    ``{``    ` `        ``// Sort the array``        ``Arrays.sort(arr);``    ` `        ``// Keep a count of the length of the``        ``// subsequence and the previous element``        ``int` `count[] = ``new` `int``[n];``        ``int` `prev[] = ``new` `int``[n];``    ` `        ``int` `i, j;``        ` `        ``// Set the initial values``        ``for``(i = ``0` `; i < n; i++)``        ``count[i] = ``1``;``        ` `        ``for``(j = ``0``; j < n; j++)``            ``prev[j] = -``1``;``    ` `        ``// Maximum length of the subsequence and``        ``// the last element``        ``int` `max = ``0``;``        ``int` `maxprev = -``1``;``    ` `        ``// Run a loop for every element``        ``for` `( i = ``0``; i < n; i++)``        ``{``    ` `            ``// Check for all the divisors``            ``for` `( j = i - ``1``; j >= ``0``; j--)``            ``{``    ` `                ``// If the element is a divisor and``                ``// the length of subsequence will``                ``// increase by adding j as``                ``// previous element of i``                ``if` `(arr[i] % arr[j] == ``0` `&&``                    ``count[j] + ``1` `> count[i])``                ``{``    ` `                    ``// Increase the count``                    ``count[i] = count[j] + ``1``;``                    ``prev[i] = j;``                ``}``            ``}``    ` `            ``// Update the max count``            ``if` `(max < count[i])``            ``{``                ``max = count[i];``                ``maxprev = i;``            ``}``        ``}``    ` `        ``// Get the last index of the subsequence``        ``i = maxprev;``        ``while` `(i >= ``0``)``        ``{``    ` `            ``// Print the element``            ``if` `(arr[i] != -``1``)``                ``System.out.print(arr[i] + ``" "``);``    ` `            ``// Move the index to the previous element``            ``i = prev[i];``        ``}``    ``}``    ` `    ``// Driver code``    ``public` `static` `void` `main (String[] args)``    ``{``        ``int` `arr[] = { ``1``, ``2``, ``3``, ``4``, ``5` `};``        ``int` `n = arr.length;``    ` `        ``findSubSeq(arr, n);``    ``}``}` `// This code is contributed by AnkitRai01`

## Python3

 `# Python3 implementation of the approach` `# Function to find the required subsequence``def` `findSubSeq(arr, n) :` `    ``# Sort the array``    ``arr.sort();` `    ``# Keep a count of the length of the``    ``# subsequence and the previous element``    ``# Set the initial values``    ``count ``=` `[``1``] ``*` `n;``    ``prev ``=` `[``-``1``] ``*` `n;` `    ``# Maximum length of the subsequence and``    ``# the last element``    ``max` `=` `0``;``    ``maxprev ``=` `-``1``;` `    ``# Run a loop for every element``    ``for` `i ``in` `range``(n) :` `        ``# Check for all the divisors``        ``for` `j ``in` `range``(i ``-` `1``, ``-``1``, ``-``1``) :` `            ``# If the element is a divisor and the length``            ``# of subsequence will increase by adding``            ``# j as previous element of i``            ``if` `(arr[i] ``%` `arr[j] ``=``=` `0` `and``                ``count[j] ``+` `1` `> count[i]) :` `                ``# Increase the count``                ``count[i] ``=` `count[j] ``+` `1``;``                ``prev[i] ``=` `j;` `        ``# Update the max count``        ``if` `(``max` `< count[i]) :``            ``max` `=` `count[i];``            ``maxprev ``=` `i;``            ` `    ``# Get the last index of the subsequence``    ``i ``=` `maxprev;``    ``while` `(i >``=` `0``) :` `        ``# Print the element``        ``if` `(arr[i] !``=` `-``1``) :``            ``print``(arr[i], end ``=` `" "``);` `        ``# Move the index to the previous element``        ``i ``=` `prev[i];` `# Driver code``if` `__name__ ``=``=` `"__main__"` `:` `    ``arr ``=` `[ ``1``, ``2``, ``3``, ``4``, ``5` `];``    ``n ``=` `len``(arr);` `    ``findSubSeq(arr, n);``    ` `# This code is contributed by AnkitRai01`

## C#

 `// C# implementation of the approach``using` `System;``using` `System.Collections;` `class` `GFG``{``    ` `    ``// Function to find the required subsequence``    ``static` `void` `findSubSeq(``int` `[]arr, ``int` `n)``    ``{``    ` `        ``// Sort the array``        ``Array.Sort(arr);``    ` `        ``// Keep a count of the length of the``        ``// subsequence and the previous element``        ``int` `[]count = ``new` `int``[n];``        ``int` `[]prev = ``new` `int``[n];``    ` `        ``int` `i, j;``        ` `        ``// Set the initial values``        ``for``(i = 0; i < n; i++)``        ``count[i] = 1;``        ` `        ``for``(j = 0; j < n; j++)``            ``prev[j] = -1;``    ` `        ``// Maximum length of the subsequence ``        ``// and the last element``        ``int` `max = 0;``        ``int` `maxprev = -1;``    ` `        ``// Run a loop for every element``        ``for` `( i = 0; i < n; i++)``        ``{``    ` `            ``// Check for all the divisors``            ``for` `( j = i - 1; j >= 0; j--)``            ``{``    ` `                ``// If the element is a divisor and``                ``// the length of subsequence will``                ``// increase by adding j as``                ``// previous element of i``                ``if` `(arr[i] % arr[j] == 0 &&``                    ``count[j] + 1 > count[i])``                ``{``    ` `                    ``// Increase the count``                    ``count[i] = count[j] + 1;``                    ``prev[i] = j;``                ``}``            ``}``    ` `            ``// Update the max count``            ``if` `(max < count[i])``            ``{``                ``max = count[i];``                ``maxprev = i;``            ``}``        ``}``    ` `        ``// Get the last index of the subsequence``        ``i = maxprev;``        ``while` `(i >= 0)``        ``{``    ` `            ``// Print the element``            ``if` `(arr[i] != -1)``                ``Console.Write(arr[i] + ``" "``);``    ` `            ``// Move the index to the previous element``            ``i = prev[i];``        ``}``    ``}``    ` `    ``// Driver code``    ``public` `static` `void` `Main ()``    ``{``        ``int` `[]arr = { 1, 2, 3, 4, 5 };``        ``int` `n = arr.Length;``    ` `        ``findSubSeq(arr, n);``    ``}``}` `// This code is contributed by AnkitRai01`

## Javascript

 ``
Output:
`4 2 1`

Time Complexity: O(N2)

Auxiliary Space: O(1)

My Personal Notes arrow_drop_up
The text passage describes a problem statement and provides a solution for finding the largest subset of an array where every pair of numbers in the subset has one number that is a divisor of the other. The passage includes examples, an explanation of the approach using dynamic programming, and code implementations in C++, Java, Python, and C#.
no_question

the passage does not contain a direct mathematical question or a specific problem to solve, but rather presents a problem statement and its solution. it does not ask the reader to solve a particular instance of the problem or provide an answer to a specific question.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Find the Largest divisor Subset in the Array

• Difficulty Level : Medium
• Last Updated : 05 Jun, 2021

Given an array arr[] of N integers, the task is to find the largest subset of arr[] such that in every pair of numbers from that subset, one number is a divisor of the other.
Examples:

Input: arr[] = {1, 2, 3, 4, 5}
Output: 4 2 1
All possible pairs of the subsequence are:
(4, 2) -> 4 % 2 = 0
(4, 1) -> 4 % 1 = 0
and (2, 1) -> 2 % 1 = 0
Input: arr[] = {1, 3, 4, 9}
Output: 1 3 9

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Approach: Here the task is to find the largest subset where in every pair of numbers, one is divisible by the other i.e. for the sequence a1, a2, a3 … ak where a1 â‰¤ a2 â‰¤ … â‰¤ ak and ai+1 % ai = 0 for every i. This sequence can be found using dynamic programming (similar to longest increasing subsequence).
Below is the implementation of the above approach:

## C++

 `// C++ implementation of the approach``#include ``using` `namespace` `std;` `// Function to find the required subsequence``void` `findSubSeq(``int` `arr[], ``int` `n)``{` `    ``// Sort the array``    ``sort(arr, arr + n);` `    ``// Keep a count of the length of the``    ``// subsequence and the previous element``    ``int` `count[n] = { 1 };``    ``int` `prev[n] = { -1 };` `    ``// Set the initial values``    ``memset``(count, 1, ``sizeof``(count));``    ``memset``(prev, -1, ``sizeof``(prev));` `    ``// Maximum length of the subsequence and``    ``// the last element``    ``int` `max = 0;``    ``int` `maxprev = -1;` `    ``// Run a loop for every element``    ``for` `(``int` `i = 0; i < n; i++) {` `        ``// Check for all the divisors``        ``for` `(``int` `j = i - 1; j >= 0; j--) {` `            ``// If the element is a divisor and the length``            ``// of subsequence will increase by adding``            ``// j as previous element of i``            ``if` `(arr[i] % arr[j] == 0``                ``&& count[j] + 1 > count[i]) {` `                ``// Increase the count``                ``count[i] = count[j] + 1;``                ``prev[i] = j;``            ``}``        ``}` `        ``// Update the max count``        ``if` `(max < count[i]) {``            ``max = count[i];``            ``maxprev = i;``        ``}``    ``}` `    ``// Get the last index of the subsequence``    ``int` `i = maxprev;``    ``while` `(i >= 0) {` `        ``// Print the element``        ``if` `(arr[i] != -1)``            ``cout << arr[i] << ``" "``;` `        ``// Move the index to the previous element``        ``i = prev[i];``    ``}``}` `// Driver code``int` `main()``{``    ``int` `arr[] = { 1, 2, 3, 4, 5 };``    ``int` `n = ``sizeof``(arr) / ``sizeof``(``int``);` `    ``findSubSeq(arr, n);` `    ``return` `0;``}`

## Java

 `// Java implementation of the approach``import` `java.util.*;``class` `GFG``{``    ` `    ``// Function to find the required subsequence``    ``static` `void` `findSubSeq(``int` `arr[], ``int` `n)``    ``{``    ` `        ``// Sort the array``        ``Arrays.sort(arr);``    ` `        ``// Keep a count of the length of the``        ``// subsequence and the previous element``        ``int` `count[] = ``new` `int``[n];``        ``int` `prev[] = ``new` `int``[n];``    ` `        ``int` `i, j;``        ` `        ``// Set the initial values``        ``for``(i = ``0` `; i < n; i++)``        ``count[i] = ``1``;``        ` `        ``for``(j = ``0``; j < n; j++)``            ``prev[j] = -``1``;``    ` `        ``// Maximum length of the subsequence and``        ``// the last element``        ``int` `max = ``0``;``        ``int` `maxprev = -``1``;``    ` `        ``// Run a loop for every element``        ``for` `( i = ``0``; i < n; i++)``        ``{``    ` `            ``// Check for all the divisors``            ``for` `( j = i - ``1``; j >= ``0``; j--)``            ``{``    ` `                ``// If the element is a divisor and``                ``// the length of subsequence will``                ``// increase by adding j as``                ``// previous element of i``                ``if` `(arr[i] % arr[j] == ``0` `&&``                    ``count[j] + ``1` `> count[i])``                ``{``    ` `                    ``// Increase the count``                    ``count[i] = count[j] + ``1``;``                    ``prev[i] = j;``                ``}``            ``}``    ` `            ``// Update the max count``            ``if` `(max < count[i])``            ``{``                ``max = count[i];``                ``maxprev = i;``            ``}``        ``}``    ` `        ``// Get the last index of the subsequence``        ``i = maxprev;``        ``while` `(i >= ``0``)``        ``{``    ` `            ``// Print the element``            ``if` `(arr[i] != -``1``)``                ``System.out.print(arr[i] + ``" "``);``    ` `            ``// Move the index to the previous element``            ``i = prev[i];``        ``}``    ``}``    ` `    ``// Driver code``    ``public` `static` `void` `main (String[] args)``    ``{``        ``int` `arr[] = { ``1``, ``2``, ``3``, ``4``, ``5` `};``        ``int` `n = arr.length;``    ` `        ``findSubSeq(arr, n);``    ``}``}` `// This code is contributed by AnkitRai01`

## Python3

 `# Python3 implementation of the approach` `# Function to find the required subsequence``def` `findSubSeq(arr, n) :` `    ``# Sort the array``    ``arr.sort();` `    ``# Keep a count of the length of the``    ``# subsequence and the previous element``    ``# Set the initial values``    ``count ``=` `[``1``] ``*` `n;``    ``prev ``=` `[``-``1``] ``*` `n;` `    ``# Maximum length of the subsequence and``    ``# the last element``    ``max` `=` `0``;``    ``maxprev ``=` `-``1``;` `    ``# Run a loop for every element``    ``for` `i ``in` `range``(n) :` `        ``# Check for all the divisors``        ``for` `j ``in` `range``(i ``-` `1``, ``-``1``, ``-``1``) :` `            ``# If the element is a divisor and the length``            ``# of subsequence will increase by adding``            ``# j as previous element of i``            ``if` `(arr[i] ``%` `arr[j] ``=``=` `0` `and``                ``count[j] ``+` `1` `> count[i]) :` `                ``# Increase the count``                ``count[i] ``=` `count[j] ``+` `1``;``                ``prev[i] ``=` `j;` `        ``# Update the max count``        ``if` `(``max` `< count[i]) :``            ``max` `=` `count[i];``            ``maxprev ``=` `i;``            ` `    ``# Get the last index of the subsequence``    ``i ``=` `maxprev;``    ``while` `(i >``=` `0``) :` `        ``# Print the element``        ``if` `(arr[i] !``=` `-``1``) :``            ``print``(arr[i], end ``=` `" "``);` `        ``# Move the index to the previous element``        ``i ``=` `prev[i];` `# Driver code``if` `__name__ ``=``=` `"__main__"` `:` `    ``arr ``=` `[ ``1``, ``2``, ``3``, ``4``, ``5` `];``    ``n ``=` `len``(arr);` `    ``findSubSeq(arr, n);``    ` `# This code is contributed by AnkitRai01`

## C#

 `// C# implementation of the approach``using` `System;``using` `System.Collections;` `class` `GFG``{``    ` `    ``// Function to find the required subsequence``    ``static` `void` `findSubSeq(``int` `[]arr, ``int` `n)``    ``{``    ` `        ``// Sort the array``        ``Array.Sort(arr);``    ` `        ``// Keep a count of the length of the``        ``// subsequence and the previous element``        ``int` `[]count = ``new` `int``[n];``        ``int` `[]prev = ``new` `int``[n];``    ` `        ``int` `i, j;``        ` `        ``// Set the initial values``        ``for``(i = 0; i < n; i++)``        ``count[i] = 1;``        ` `        ``for``(j = 0; j < n; j++)``            ``prev[j] = -1;``    ` `        ``// Maximum length of the subsequence ``        ``// and the last element``        ``int` `max = 0;``        ``int` `maxprev = -1;``    ` `        ``// Run a loop for every element``        ``for` `( i = 0; i < n; i++)``        ``{``    ` `            ``// Check for all the divisors``            ``for` `( j = i - 1; j >= 0; j--)``            ``{``    ` `                ``// If the element is a divisor and``                ``// the length of subsequence will``                ``// increase by adding j as``                ``// previous element of i``                ``if` `(arr[i] % arr[j] == 0 &&``                    ``count[j] + 1 > count[i])``                ``{``    ` `                    ``// Increase the count``                    ``count[i] = count[j] + 1;``                    ``prev[i] = j;``                ``}``            ``}``    ` `            ``// Update the max count``            ``if` `(max < count[i])``            ``{``                ``max = count[i];``                ``maxprev = i;``            ``}``        ``}``    ` `        ``// Get the last index of the subsequence``        ``i = maxprev;``        ``while` `(i >= 0)``        ``{``    ` `            ``// Print the element``            ``if` `(arr[i] != -1)``                ``Console.Write(arr[i] + ``" "``);``    ` `            ``// Move the index to the previous element``            ``i = prev[i];``        ``}``    ``}``    ` `    ``// Driver code``    ``public` `static` `void` `Main ()``    ``{``        ``int` `[]arr = { 1, 2, 3, 4, 5 };``        ``int` `n = arr.Length;``    ` `        ``findSubSeq(arr, n);``    ``}``}` `// This code is contributed by AnkitRai01`

## Javascript

 ``
Output:
`4 2 1`

Time Complexity: O(N2)

Auxiliary Space: O(1)

My Personal Notes arrow_drop_up
user
The text passage describes a problem statement and provides a solution for finding the largest subset of an array where every pair of numbers in the subset has one number that is a divisor of the other. The passage includes examples, an explanation of the approach using dynamic programming, and code implementations in C++, Java, Python, and C#.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question or a specific problem to solve, but rather presents a problem statement and its solution. It does not ask the reader to solve a particular instance of the problem or provide an answer to a specific question.