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 = 0Input: arr[] = {1, 3, 4, 9}
Output: 1 3 9
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 <bits/stdc++.h>using namespace std;// Function to find the required subsequencevoid 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 codeint 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
<script>// Javascript implementation of above approach// Function to find the required subsequencefunction findSubSeq(arr, n){ // Sort the array arr.sort(); // Keep a count of the length of the // subsequence and the previous element var count = new Array(n); var prev = new Array(n); // Set the initial values count.fill(1); prev.fill(-1); // Maximum length of the subsequence and // the last element var max = 0; var maxprev = -1; // Run a loop for every element for (var i = 0; i < n; i++) { // Check for all the divisors for (var 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 var i = maxprev; while (i >= 0) { // Print the element if (arr[i] != -1) document.write( arr[i] + " "); // Move the index to the previous element i = prev[i]; }}var arr = [ 1, 2, 3, 4, 5 ];var n = arr.length;findSubSeq(arr, n);//This code is contributed by SoumikMondal</script> |
Output
4 2 1
Time Complexity: O(N2), where N is the length of the given array.
Auxiliary Space: O(N)
Approach(Dynamic programming):
The approach uses dynamic programming to find the largest subset of an array such that in every pair of numbers from that subset, one number is a divisor of the other. It initializes a dp array with 1’s as the minimum size of a subset is 1. It then iterates over each element in the array and checks for all its divisors if there is a larger subset ending at that divisor index. If a larger subset is found, it updates the dp[i] with the new maximum value. Finally, it returns the largest subset by backtracking through the dp array.
here’s the full implementation of the code:
C++
#include <bits/stdc++.h>using namespace std;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; } } // Print the largest divisor subset in reverse order int i = maxprev; while (i >= 0) { cout << arr[i] << " "; i = prev[i]; }}int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr) / sizeof(int); findSubSeq(arr, n); return 0;} |
Java
import java.util.Arrays;public class FindSubSeq { public 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]; // Set the initial values Arrays.fill(count, 1); Arrays.fill(prev, -1); // 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; } } // Print the largest divisor subset in reverse order int i = maxprev; while (i >= 0) { System.out.print(arr[i] + " "); i = prev[i]; } } public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5 }; int n = arr.length; findSubSeq(arr, n); }} |
Python3
def findSubSeq(arr, n): # Sort the array arr.sort() # Keep a count of the length of the subsequence and the previous element 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 # Print the largest divisor subset in reverse order i = maxprev while i >= 0: print(arr[i], end=" ") i = prev[i]arr = [1, 2, 3, 4, 5]n = len(arr)findSubSeq(arr, n) |
C#
using System;class GFG{ static void FindSubsequence(int[] arr, int n) { // Sort the array Array.Sort(arr); // Arrays to store the count of elements in the // subsequence and their previous element indices int[] count = new int[n]; int[] prev = new int[n]; // Initialize the count and previous arrays with default values Array.Fill(count, 1); Array.Fill(prev, -1); // Variables to keep track of the maximum length of the // subsequence and its last element's index int max = 0; int maxprev = -1; // Loop for each element in the array for (int i = 0; i < n; i++) { // Check for all elements before the current element for (int j = i - 1; j >= 0; j--) { // If arr[i] is divisible by arr[j] and the subsequence will // be longer by adding j as the previous element of i if (arr[i] % arr[j] == 0 && count[j] + 1 > count[i]) { // Update the count and previous element index count[i] = count[j] + 1; prev[i] = j; } } // Update the maximum count and the index of the last element // in the longest subsequence if (max < count[i]) { max = count[i]; maxprev = i; } } // Print the largest divisor subset in reverse order int idx = maxprev; while (idx >= 0) { Console.Write(arr[idx] + " "); idx = prev[idx]; } } static void Main() { int[] arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; FindSubsequence(arr, n); }} |
Javascript
function findSubSeq(arr) { const n = arr.length; // Sort the array arr.sort((a, b) => a - b); // Keep a count of the length of the subsequence and the previous element const count = new Array(n).fill(1); const prev = new Array(n).fill(-1); // Maximum length of the subsequence and the last element let max = 0; let maxprev = -1; // Run a loop for every element for (let i = 0; i < n; i++) { // Check for all the divisors for (let j = i - 1; j >= 0; j--) { // If the element is a divisor and the length of subsequence will increase // by adding j as the 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; } } // Print the largest divisor subset in order let result = []; let i = maxprev; while (i >= 0) { result.push(arr[i]); i = prev[i]; } console.log(result.join(" "));}const arr = [1, 2, 3, 4, 5];findSubSeq(arr); |
Output
4 2 1
Time Complexity: O(n^2) due to the nested loops used to check all possible divisors.
Auxiliary Space: O(n) to store the count and prev arrays.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!