[Dynamic Programming] Largest Divisible Subset - Medium

The Largest Divisible Subset problem is a well-known challenge in dynamic programming. The goal is to find the biggest group of numbers from a set. In this group, every number can divide the other numbers evenly. To solve this problem, we apply a dynamic programming method. This method keeps track of the length of the largest divisible subset that ends at each number. Later, we can use this information to build the subset.

In this article, we will look closely at the dynamic programming method for solving the Largest Divisible Subset problem. First, we will understand the problem. Then, we will provide detailed solutions using dynamic programming in Java, Python, and C++. We will also talk about ways to make the dynamic programming approach better. We will analyze the time and space needed for the solution. We will discuss other ways to solve the problem too. Finally, we will answer some common questions about this topic.

  • Dynamic Programming Approach for Largest Divisible Subset Problem
  • Understanding the Problem Statement for Largest Divisible Subset
  • Dynamic Programming Solution in Java for Largest Divisible Subset
  • Dynamic Programming Solution in Python for Largest Divisible Subset
  • Dynamic Programming Solution in C++ for Largest Divisible Subset
  • Optimizing the Dynamic Programming Approach for Largest Divisible Subset
  • Time Complexity Analysis of Largest Divisible Subset Solution
  • Space Complexity Considerations in Largest Divisible Subset
  • Alternative Approaches to Solve Largest Divisible Subset
  • Frequently Asked Questions

If you want to explore more dynamic programming problems, you may find articles like Dynamic Programming on Fibonacci Numbers or Dynamic Programming on Unique Paths in a Grid helpful for more reading.

Understanding the Problem Statement for Largest Divisible Subset

The Largest Divisible Subset problem is about finding the biggest group of numbers from a set. In this group, every pair of numbers can divide each other.

Problem Definition

We have a set of numbers. Our goal is to find the largest group. In this group, for every pair (Si, Sj), either Si % Sj == 0 or Sj % Si == 0.

Example

For the input set:

[1, 2, 3, 4, 6, 12]

The biggest divisible group is:

[1, 2, 4, 12]

Input and Output

  • Input: An array of numbers nums.
  • Output: An array of numbers that show the largest divisible group.

Constraints

  • The input array can have up to 1000 numbers.
  • Each number can be from 1 to 10^9.

We need to understand this problem. Then we can use a dynamic programming method to find the largest divisible group in a smart way.

Dynamic Programming Solution in Java for Largest Divisible Subset

We can solve the Largest Divisible Subset problem using Dynamic Programming in Java. We follow a simple plan. First, we sort the numbers. Then, we use a dynamic programming array to find the size of the largest divisible subset that ends with each number.

Here is the Java code for this method:

import java.util.Arrays;

public class LargestDivisibleSubset {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 6, 12};
        System.out.println("Largest Divisible Subset: " + largestDivisibleSubset(nums));
    }

    public static String largestDivisibleSubset(int[] nums) {
        if (nums.length == 0) return "[]";
        
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);
        
        int maxSize = 1;
        int maxIndex = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > maxSize) {
                maxSize = dp[i];
                maxIndex = i;
            }
        }

        StringBuilder result = new StringBuilder();
        while (maxIndex >= 0) {
            result.insert(0, nums[maxIndex] + " ");
            maxIndex = prev[maxIndex];
        }

        return "[" + result.toString().trim() + "]";
    }
}

Explanation:

  • Sorting: We sort the array first. This helps us build the subset in the right order.
  • DP Array: The dp array saves the size of the largest divisible subset that ends with the number at that position.
  • Prev Array: The prev array keeps the previous index in the largest subset for rebuilding it later.
  • Nested Loops: The outer loop goes through each number. The inner loop checks each previous number to see if it divides.
  • Result Construction: We build the result by going back through the prev array from the index of the largest divisible subset.

This way, we can find the largest divisible subset in (O(n^2)) time. Here, (n) is the length of the input array.

For more practice with dynamic programming, we can check this Dynamic Programming - Longest Increasing Subsequence.

Dynamic Programming Solution in Python for Largest Divisible Subset

To solve the Largest Divisible Subset problem with dynamic programming in Python, we can do these steps:

  1. Sort the Input Array: First, we sort the input array. This makes sure that if arr[j] is divisible by arr[i], then j is always bigger than i.

  2. Initialize DP Array: We create a dynamic programming array called dp. Here, dp[i] shows the size of the largest divisible subset that ends with arr[i]. We also keep a prev array to help us get the subset later.

  3. Fill DP Array: We go through the sorted array. For each element, we check all previous elements to see if they can make a divisible pair. We update the dp and prev arrays when needed.

  4. Reconstruct the Subset: After we fill the dp array, we look for the biggest number in dp to find the size of the largest divisible subset. We then use the prev array to get the actual subset.

Here is the code in Python:

def largestDivisibleSubset(nums):
    if not nums:
        return []

    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n

    max_size = 1
    max_index = 0

    for i in range(n):
        for j in range(i):
            if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j
        
        if dp[i] > max_size:
            max_size = dp[i]
            max_index = i

    # Reconstruct the largest divisible subset
    result = []
    while max_index != -1:
        result.append(nums[max_index])
        max_index = prev[max_index]

    return result[::-1]  # Return in the correct order

# Example usage
nums = [1, 2, 3, 4, 6, 12]
print(largestDivisibleSubset(nums))  # Output: [1, 2, 4, 12]

Explanation of the Code:

  • The largestDivisibleSubset function takes a list of numbers called nums.
  • It sorts the list and sets up the dp and prev arrays.
  • It goes through each item and checks if it can divide with earlier items.
  • Finally, we build the largest divisible subset by going back using the prev array.

This dynamic programming method finds the largest divisible subset in O(n^2) time. This makes it good for input arrays of moderate size. For more information on dynamic programming methods, we can check the Dynamic Programming: Longest Increasing Subsequence article.

Dynamic Programming Solution in C++ for Largest Divisible Subset

To solve the Largest Divisible Subset problem using dynamic programming in C++, we can do these steps:

  1. Sort the Input Array: First, we sort the array. This helps us make the largest divisible subset. It ensures that if nums[j] is divisible by nums[i], then j is greater than i.

  2. Initialize Arrays: We create a dp array. This array stores the size of the largest divisible subset that ends with the element at index i. We also create a prev array to help us find the subset later.

  3. Fill the DP Table: We go through each pair of indexes. We update the dp values based on the divisibility rules.

  4. Find the Maximum Subset Size: After filling the dp array, we find the index of the maximum value. This helps us to reconstruct the subset.

  5. Reconstruct the Subset: Using the prev array, we backtrack to find the actual elements of the largest divisible subset.

Here is the complete C++ code:

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> largestDivisibleSubset(std::vector<int>& nums) {
    if (nums.empty()) return {};

    std::sort(nums.begin(), nums.end());
    std::vector<int> dp(nums.size(), 1);
    std::vector<int> prev(nums.size(), -1);
    int maxIndex = 0;

    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > dp[maxIndex]) {
            maxIndex = i;
        }
    }

    std::vector<int> result;
    for (int k = maxIndex; k >= 0; k = prev[k]) {
        result.push_back(nums[k]);
        if (prev[k] == -1) break;
    }

    std::reverse(result.begin(), result.end());
    return result;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 6};
    std::vector<int> result = largestDivisibleSubset(nums);
    
    std::cout << "Largest Divisible Subset: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    return 0;
}

Explanation of the Code:

  • Sorting: We sort the array. This makes sure we check divisibility in the right order.
  • Dynamic Programming Logic: The nested loop checks each pair of elements. It updates the dp and prev arrays.
  • Reconstruction: We build the result by going back from the index of the maximum dp value.

This C++ solution computes the largest divisible subset. It uses dynamic programming to make the search and retrieval easy. For more information on dynamic programming, we can read articles like Dynamic Programming - Longest Increasing Subsequence.

Optimizing the Dynamic Programming Approach for Largest Divisible Subset

We can make the Dynamic Programming (DP) method for the Largest Divisible Subset problem better. We will sort the input array and use a better data structure for the DP state.

Steps for Optimization:

  1. Sort the Input Array: Sorting helps us see which numbers divide each other. If arr[i] divides arr[j] and i > j, then arr[i] can join the subset with arr[j].

  2. Use a DP Array: We create a DP array. Here, dp[i] shows the size of the largest divisible subset that ends with arr[i]. We start each entry at 1 because every number can at least be its own subset.

  3. Backtracking Array: We also keep a prev array. This tracks the previous index of the elements in the subset. It helps us build the subset later.

  4. Iterate and Update: For each element, we check all previous elements. We find the largest subset size that can include the current element. We then update the dp and prev arrays.

Optimized Code Example in Java:

import java.util.*;

public class LargestDivisibleSubset {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length == 0) return Collections.emptyList();
        
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);
        
        int maxIndex = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }
        
        List<Integer> result = new ArrayList<>();
        for (int k = maxIndex; k >= 0; k = prev[k]) {
            result.add(nums[k]);
            if (prev[k] == -1) break;
        }
        Collections.reverse(result);
        return result;
    }
}

Optimized Code Example in Python:

def largestDivisibleSubset(nums):
    if not nums:
        return []
    
    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    
    max_index = 0
    for i in range(n):
        for j in range(i):
            if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j
        if dp[i] > dp[max_index]:
            max_index = i
            
    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    
    return result[::-1]

Optimized Code Example in C++:

#include <vector>
#include <algorithm>

std::vector<int> largestDivisibleSubset(std::vector<int>& nums) {
    if (nums.empty()) return {};
    
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    std::vector<int> dp(n, 1), prev(n, -1);
    
    int max_index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > dp[max_index]) {
            max_index = i;
        }
    }
    
    std::vector<int> result;
    while (max_index >= 0) {
        result.push_back(nums[max_index]);
        max_index = prev[max_index];
    }
    std::reverse(result.begin(), result.end());
    return result;
}

Complexity Analysis:

  • Time Complexity: O(n^2) because of the nested loops that go through the elements.
  • Space Complexity: O(n) since we need to store the dp and prev arrays.

This way, we find the largest divisible subset in an efficient way. The code is clear and easy to follow. For more dynamic programming problems, you can read articles on Dynamic Programming: Fibonacci Number and Dynamic Programming: Longest Increasing Subsequence.

Time Complexity Analysis of Largest Divisible Subset Solution

We can look at the time complexity of the Largest Divisible Subset problem when we solve it with dynamic programming.

  1. Sorting the Input:
    • First, we need to sort the input array. This sorting takes (O(n n)) time. Here (n) is the number of items in the array.
  2. Dynamic Programming Computation:
    • After we sort, we use a loop inside another loop to fill the dynamic programming array. For each element (i) in the sorted array, we check all the earlier elements (j) (where (j < i)). We see if (nums[i]) can be divided by (nums[j]). This part can take (O(n^2)) time in the worst case. This is because we might need to compare each item with all other items.
  3. Building the Result:
    • To build the largest subset from the DP array, we need linear time (O(n)). We trace back through the array to get the final subset.

When we combine these steps, the total time complexity of the dynamic programming solution for the Largest Divisible Subset problem is:

[ O(n n) + O(n^2) + O(n) = O(n^2) ]

So, the main term we focus on is (O(n^2)).

This speed is usually okay for medium values of (n). So, the dynamic programming method is a good choice for solving the Largest Divisible Subset problem.

Space Complexity Considerations in Largest Divisible Subset

In the Largest Divisible Subset problem, space complexity is very important. It helps us see how well our dynamic programming method works. The main things using space are the dynamic programming array and other data structures we might need.

Space Complexity Breakdown

  1. Dynamic Programming Array:
    • We use an array dp. This array tells us the size of the largest divisible subset that ends with the element at index i. The size of this array is n, where n is the number of elements in the input array.
    • So, the space complexity for this array is O(n).
  2. Tracking Pointers:
    • To find the actual subset later, we might need another array called prev. This array holds the indices of previous elements in the subset. This also takes O(n) space.
  3. Total Space Complexity:
    • The total space complexity of the algorithm is O(n) + O(n) = O(n).

Optimized Space Usage

If memory is really tight, we can use just one array. We can then find the subset without needing the full prev array. But this makes it harder to reconstruct the subset. We usually do not recommend this unless we have to.

Example Calculation

Let’s say we have an input array nums = [1, 2, 3, 4, 6]:

int n = nums.length;
int[] dp = new int[n]; // O(n) space
int[] prev = new int[n]; // O(n) space for tracking previous indices

This gives us a total space complexity of O(n). This is good for normal limits in competitions and interviews.

In short, the space complexity for the Largest Divisible Subset problem mainly comes from the size of the dynamic programming array and other arrays. Together, they give a total space complexity of O(n).

For more information on dynamic programming, we can check out articles like Dynamic Programming - Maximum Subarray (Kadane’s Algorithm) and Dynamic Programming - Longest Increasing Subsequence.

Alternative Approaches to Solve Largest Divisible Subset

We can solve the Largest Divisible Subset problem with different methods. The dynamic programming approach is good, but other ways can also work. These methods might not be the best, but they are worth knowing. Here are some of them:

  1. Greedy Approach:
    • We can use a greedy approach to build a subset step by step. But this may not always give us the largest divisible subset. First, we sort the array. Then, we add numbers to the subset based on if they divide each other.
  2. Backtracking:
    • Backtracking lets us check all possible subsets and see if they meet the divisibility rules. This method looks at every subset and keeps the ones that work. But this way takes a long time for bigger inputs because it grows very fast.
    def backtrack(nums, start, subset):
    if is_valid(subset):
        result.append(subset[:])
    for i in range(start, len(nums)):
        subset.append(nums[i])
        backtrack(nums, i + 1, subset)
        subset.pop()
  3. Bit Manipulation:
    • We can use bit manipulation to create all possible subsets of the input array. Each bit in a number shows if we include or not include an element. But this also has a long time complexity.
    def generate_subsets(nums):
    subsets = []
    n = len(nums)
    for i in range(1 << n):
        subset = []
        for j in range(n):
            if i & (1 << j):
                subset.append(nums[j])
        subsets.append(subset)
    return subsets
  4. Graph Theory:
    • We can think of each number as a point in a directed graph. There is an arrow from point a to point b if a can divide b. Finding the largest divisible subset is like finding the longest path in this graph. But this method is tricky and may not work well in all cases.
  5. Sorting and Iteration:
    • We can sort the numbers and check for divisibility one by one. This way can help us build a possible subset. It is simple but does not always give us the largest subset.
    def largest_divisible_subset(nums):
    nums.sort()
    dp = [1] * len(nums)
    prev = [-1] * len(nums)
    max_size, max_index = 0, 0

    for i in range(len(nums)):
        for j in range(i):
            if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j
        if dp[i] > max_size:
            max_size = dp[i]
            max_index = i

    # Reconstructing the largest divisible subset
    subset = []
    while max_index >= 0:
        subset.append(nums[max_index])
        max_index = prev[max_index]
    return subset[::-1]

These different approaches give us ways to solve the Largest Divisible Subset problem. Each has its own good points and challenges with time and efficiency. If we want to learn more about dynamic programming, we can look at articles on dynamic programming and the Fibonacci sequence and longest increasing subsequences.

Frequently Asked Questions

What is the Largest Divisible Subset problem in Dynamic Programming?

The Largest Divisible Subset problem is about finding the biggest group of numbers from a set. In this group, each pair of numbers must meet a divisibility rule. This means for any two numbers a and b in the group, either a % b == 0 or b % a == 0. We use dynamic programming to build the solution step by step. We look at the sorted list and check if numbers can divide each other.

How can I implement the Largest Divisible Subset in Java?

To implement the Largest Divisible Subset problem in Java, we can use dynamic programming. We keep an array that shows the size of the largest group that ends with each number. After we fill this array, we go back to find the actual group. This method works well and takes O(n^2) time. For more details, check our Dynamic Programming Solution in Java for Largest Divisible Subset.

What is the time complexity of the Largest Divisible Subset algorithm?

The time complexity for the dynamic programming solution of the Largest Divisible Subset problem is O(n^2). This happens because we have nested loops. Each number checks against all previous numbers to see if they divide each other. Even with this complexity, this method works good for medium-sized arrays. So it is a good option for real-life tasks.

Can I solve the Largest Divisible Subset problem using Python?

Yes, we can solve the Largest Divisible Subset problem with Python. We use a similar dynamic programming method like in Java. We keep a list to track the sizes of the biggest groups and use backtracking to find the group itself. For a full guide, see our Dynamic Programming Solution in Python for Largest Divisible Subset.

Are there alternative approaches to solving the Largest Divisible Subset problem?

The dynamic programming method is the best way to solve this problem. But we can also use other methods like recursive backtracking. These other ways may not be as fast. For more information about different methods, we can look at related topics like the Longest Increasing Subsequence or the Subset Sum Problem.