Jobs

Interviews

Discussions

Largest Divisible Subset

Medium

Asked by:

51 views

Topics:

ArraysDynamic Programming

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[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 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 10⁹
All the integers in nums are unique.

Largest Divisible Subset

Medium

Asked by:

51 views

Topics:

ArraysDynamic Programming

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[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 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 10⁹
All the integers in nums are unique.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size and range of values within the `nums` array? Are we dealing with integers or floating-point numbers?
Can the input array `nums` be empty or contain null values? If so, what should I return?
If there are multiple largest divisible subsets, is there a specific criteria I should use to choose which one to return, or can I return any valid one?
Are all numbers in the input array guaranteed to be distinct, as stated, or could there be duplicates?
If no divisible subset exists with more than one element, should I return an empty list, or a list containing a single element from the input?

Brute Force Solution

Approach

The brute force strategy to find the largest divisible subset involves checking every possible combination of numbers from the input. We build up subsets and test their divisibility properties until we find the largest one. It's an exhaustive search to guarantee we consider all possibilities.

Here's how the algorithm would work step-by-step:

Start by sorting the numbers in increasing order. This helps in checking divisibility easily.
Consider each number as a potential starting point for a subset.
For each starting number, try adding other numbers from the list to form a subset.
When adding a new number, check if it's divisible by the last number added to the subset, or if the last number is divisible by the new number.
If they are divisible, add the new number to the subset; otherwise, skip it.
Keep track of the largest subset found so far.
Repeat the process with every number as a potential starting point.
After exploring all possible starting points and their subsets, return the largest subset that was found.

Code Implementation

def largest_divisible_subset_brute_force(numbers):
    numbers.sort()
    largest_subset = []

    for start_index in range(len(numbers)):
        current_subset = [numbers[start_index]]

        # Try to build the subset from this starting point
        for next_index in range(start_index + 1, len(numbers)):
            # Divisibility check to form the subset
            if numbers[next_index] % current_subset[-1] == 0 or current_subset[-1] % numbers[next_index] == 0:
                current_subset.append(numbers[next_index])

        if len(current_subset) > len(largest_subset):
            largest_subset = current_subset

    return largest_subset

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores all possible subsets of the input array. For each of the n elements, we either include it or exclude it in a potential subset. This leads to 2^n possible subsets to evaluate. Checking the divisibility within each subset takes additional time, but the dominant factor is generating and considering all 2^n subsets. Therefore, the time complexity is O(2^n).

Space Complexity

O(N) – The algorithm maintains a 'largest subset' that can grow up to the size of the input array. Also, within the main loop, temporary subsets are created to explore divisibility possibilities, and in the worst case, these could also grow to size N. Therefore, the auxiliary space used is proportional to the input size N. This results in a space complexity of O(N).

Optimal Solution

Approach

The key to finding the largest divisible subset is building it piece by piece. We start with small subsets and expand them using a strategic selection process that guarantees divisibility. This eliminates the need to check every possible combination.

Here's how the algorithm would work step-by-step:

First, sort the numbers in increasing order. This makes it easier to check for divisibility.
Think of each number as potentially being the last number in a valid divisible subset.
For each number, find the largest divisible subset that ends with that number. We can do this by looking at all the numbers before it.
Check if the current number is divisible by any of the numbers in the subsets we've already found. If it is, we can add it to that subset to make a bigger subset.
Keep track of the largest subset we've found so far.
Once we've gone through all the numbers, return the largest subset we found. It will be the largest divisible subset of the original set.

Code Implementation

def largest_divisible_subset(numbers):
    numbers.sort()
    number_of_elements = len(numbers)
    divisible_subset_sizes = [1] * number_of_elements
    previous_element_index = [-1] * number_of_elements

    # To keep track of largest subset
    max_subset_size = 1
    max_subset_index = 0

    for i in range(1, number_of_elements):
        for j in range(i):
            # Check if current number is divisible
            if numbers[i] % numbers[j] == 0:
                if divisible_subset_sizes[i] < divisible_subset_sizes[j] + 1:

                    divisible_subset_sizes[i] = divisible_subset_sizes[j] + 1
                    previous_element_index[i] = j

        # Update largest subset
        if divisible_subset_sizes[i] > max_subset_size:
            max_subset_size = divisible_subset_sizes[i]
            max_subset_index = i

    largest_subset = []
    current_index = max_subset_index

    # Backtrack to create largest subset
    while current_index != -1:

        largest_subset.append(numbers[current_index])
        current_index = previous_element_index[current_index]

    return largest_subset[::-1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first sorts the input array of size n, which typically takes O(n log n) time. After sorting, the dominant part of the algorithm involves iterating through each of the n numbers in the sorted array. For each number, we potentially iterate through all preceding numbers to find the largest divisible subset ending with that number. Thus, for each of the n numbers, we perform up to n-1 divisibility checks and subset comparisons, which contributes to O(n²) operations. The sorting step, O(n log n), is less significant than the nested loop's O(n²) complexity, so the overall time complexity is O(n²).

Space Complexity

O(N) – The space complexity is dominated by the need to store the largest divisible subset ending at each number and tracking the overall largest subset. This requires an auxiliary array, `dp`, of size N, where N is the number of elements in the input array, to store the largest divisible subset found so far ending with the element at that index. We also need to store the actual largest divisible subset, which at most, can contain N elements. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty list as there are no elements to form a subset.
Array with a single element	Return the array itself as a single element is always a divisible subset.
Array with all elements being the same value	Return the entire array as any pair will satisfy the divisibility condition.
Large input array to test efficiency (e.g., 1000+ elements)	The dynamic programming approach should scale reasonably well, but consider memory usage for storing subset lengths.
Input array contains very large numbers that could cause integer overflow during modulo operation	Ensure to use a data type that can accommodate large numbers (e.g., long) or perform modulo operations carefully to avoid overflow.
No divisible subset exists besides single elements	The algorithm should correctly identify and return the longest possible subset, even if it only contains single elements.
Multiple equally sized largest divisible subsets exist	The algorithm can return any one of the equally sized largest divisible subsets; no specific preference is required.
Array with a wide range of values and significant gaps in divisibility	The dynamic programming approach ensures that we correctly track divisibility relationships even with uneven distributions.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size and range of values within the `nums` array? Are we dealing with integers or floating-point numbers?
Can the input array `nums` be empty or contain null values? If so, what should I return?
If there are multiple largest divisible subsets, is there a specific criteria I should use to choose which one to return, or can I return any valid one?
Are all numbers in the input array guaranteed to be distinct, as stated, or could there be duplicates?
If no divisible subset exists with more than one element, should I return an empty list, or a list containing a single element from the input?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by sorting the numbers in increasing order. This helps in checking divisibility easily.
Consider each number as a potential starting point for a subset.
For each starting number, try adding other numbers from the list to form a subset.
When adding a new number, check if it's divisible by the last number added to the subset, or if the last number is divisible by the new number.
If they are divisible, add the new number to the subset; otherwise, skip it.
Keep track of the largest subset found so far.
Repeat the process with every number as a potential starting point.
After exploring all possible starting points and their subsets, return the largest subset that was found.

Code Implementation

def largest_divisible_subset_brute_force(numbers):
    numbers.sort()
    largest_subset = []

    for start_index in range(len(numbers)):
        current_subset = [numbers[start_index]]

        # Try to build the subset from this starting point
        for next_index in range(start_index + 1, len(numbers)):
            # Divisibility check to form the subset
            if numbers[next_index] % current_subset[-1] == 0 or current_subset[-1] % numbers[next_index] == 0:
                current_subset.append(numbers[next_index])

        if len(current_subset) > len(largest_subset):
            largest_subset = current_subset

    return largest_subset

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, sort the numbers in increasing order. This makes it easier to check for divisibility.
Think of each number as potentially being the last number in a valid divisible subset.
For each number, find the largest divisible subset that ends with that number. We can do this by looking at all the numbers before it.
Check if the current number is divisible by any of the numbers in the subsets we've already found. If it is, we can add it to that subset to make a bigger subset.
Keep track of the largest subset we've found so far.
Once we've gone through all the numbers, return the largest subset we found. It will be the largest divisible subset of the original set.

Code Implementation

def largest_divisible_subset(numbers):
    numbers.sort()
    number_of_elements = len(numbers)
    divisible_subset_sizes = [1] * number_of_elements
    previous_element_index = [-1] * number_of_elements

    # To keep track of largest subset
    max_subset_size = 1
    max_subset_index = 0

    for i in range(1, number_of_elements):
        for j in range(i):
            # Check if current number is divisible
            if numbers[i] % numbers[j] == 0:
                if divisible_subset_sizes[i] < divisible_subset_sizes[j] + 1:

                    divisible_subset_sizes[i] = divisible_subset_sizes[j] + 1
                    previous_element_index[i] = j

        # Update largest subset
        if divisible_subset_sizes[i] > max_subset_size:
            max_subset_size = divisible_subset_sizes[i]
            max_subset_index = i

    largest_subset = []
    current_index = max_subset_index

    # Backtrack to create largest subset
    while current_index != -1:

        largest_subset.append(numbers[current_index])
        current_index = previous_element_index[current_index]

    return largest_subset[::-1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty list as there are no elements to form a subset.
Array with a single element	Return the array itself as a single element is always a divisible subset.
Array with all elements being the same value	Return the entire array as any pair will satisfy the divisibility condition.
Large input array to test efficiency (e.g., 1000+ elements)	The dynamic programming approach should scale reasonably well, but consider memory usage for storing subset lengths.
Input array contains very large numbers that could cause integer overflow during modulo operation	Ensure to use a data type that can accommodate large numbers (e.g., long) or perform modulo operations carefully to avoid overflow.
No divisible subset exists besides single elements	The algorithm should correctly identify and return the longest possible subset, even if it only contains single elements.
Multiple equally sized largest divisible subsets exist	The algorithm can return any one of the equally sized largest divisible subsets; no specific preference is required.
Array with a wide range of values and significant gaps in divisibility	The dynamic programming approach ensures that we correctly track divisibility relationships even with uneven distributions.