Largest Divisible Subset

Problem: Given a set of distinct positive integers, return the largest subset result such that every pair (result[i], result[j]) of elements in this subset satisfies:

• answer[i] % answer[j] == 0, or
• answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Example:

Input: nums = [1,2,3,6,9,12,18]
Output: [1,2,6,12]

Approach: We can sort the array and then we can use DP here. We can maintain a 1D Table where Table[i] will tell the length of largest divisible subset in the array nums[0...i]. Here is how we can fill this table:

• Table[0] = 1
• maxLength = 1
• FOR i = 1 to n - 1
• For j = 0  to i - 1
• IF nums[i] % nums[j] == 0
• Table[i] =  MAX(Table[i], Table[j])
• Table[i] = Table[i] + 1 // For current element
• maxLength = MAX(maxLength, Table[i]

Once we have the length of largest divisible subset(maxLength), we can trace back to find the elements of largest divisible subset easily.

 

Implementation in C#: 

        public IList<int> LargestDivisibleSubset(int[] nums)

        {

            int[] table = new int[nums.Length];

            Array.Sort(nums);

            table[0] = 1;

            int maxLength = 1;

            for (int i = 1; i < nums.Length; ++i)

            {

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

                {

                    table[i] = nums[i] % nums[j] == 0 ? Math.Max(table[i], table[j]) : table[i];

                }

                ++table[i];

                maxLength = Math.Max(table[i], maxLength);

            }

            int prevNum = -1;

            List<int> result = new List<int>();

            for (int i = nums.Length - 1; i >= 0; --i)

            {

                if (table[i] == maxLength && (prevNum ==  -1 || prevNum % nums[i] == 0))

                {

                    result.Add(nums[i]);

                    prevNum = nums[i];

                    --maxLength;

                }

            }

            return result;

        }

Complexity: O(n^2)