DP-Interviews
  • Dynamic Programming
  • Notes
    • Equal Subset Sum Partition
    • Longest Increasing Subsequence
    • Maximum Ribbon Cut
    • Largest Divisible Subset
    • Longest Common Substring
    • Unbounded Knapsack
    • Minimum Coin Change
    • Coin Change
    • Target Sum
    • Minimum Subset Sum Difference
    • Rod Cutting
    • Longest Palindromic Substring
    • Longest Bitonic Sequence
    • Longest Repeating Sequence
    • Longest String Chain
    • Natarajan's Birthday Bombs
    • Subsequence Pattern Matching
    • Russian Doll
    • Buy & Sell Stock
    • Maximum Sum Increasing Subsequence
    • Longest Common Subsequence
    • Shortest Common Supersequence
    • 0/1 Knapsack Problem
    • Best Team With No Conflict
    • Count Subset Sum
    • Edit Distance
    • Box-Stacking
    • Longest Palindromic Subsequence
    • All Possible Cuts In All Possible Intervals For Choosing Last Operation
    • Minimum Deletions & Insertions To Transform a String into another
    • Regular Expression Matching
    • Wildcard Matching
    • Optimal Paths To Target
Powered by GitBook
On this page

Was this helpful?

  1. Notes

Largest Divisible Subset

PreviousMaximum Ribbon CutNextLongest Common Substring

Last updated 3 years ago

Was this helpful?

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, returning any subset is fine.

Example 1:

Input: [1,2,3]
Output: [1,2] or [1,3]

Solution

The below two observations would help us to come up with our algorithm to solve this problem:

Given a list of values [E, F, G] sorted in ascending order (i.e. E < F < G), and the list itself forms a divisible subset as described in the problem, then we could extend the subset without enumerating all numbers in the subset, in the following two cases:

  1. For any value that can be divided by the largest element in the divisible subset, by adding the new value into the subset, one can form another divisible subset, i.e. for all h, if h % G == 0, then [E, F, G, h] forms a new divisible subset. Example: [2, 4, 8] is a divisible list. Now 40 % 8 = 0, and the list [2, 4, 8, 40] is also divisible.

  2. For all value that can divide the smallest element in the subset, by adding the new value into the subset, one can form another divisible subset, i.e. for all d, if E % d == 0, then [d, E, F, G] forms a new divisible subset. Example: [4, 8, 16] is a divisible list. Now 2 % 4 = 0, and the list [2, 4, 8, 16] is also divisible.

We sort the given integer array in ascending sort. Now the Longest Increasing Subsequence of the sorted array maintaining the given divisibility condition would give us the largest divisible subset, as shown in the code.

Code