Largest Divisible Subset - Practice Coding Problems

Largest Divisible Subset - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,6]

› Output: [1,2,6]

💡 Note: Clear step-by-step: 1 divides 2 (2%1=0), 2 divides 6 (6%2=0), and 1 divides 6 (6%1=0). All pairs satisfy divisibility.

Example 2 — Alternative Chain

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

› Output: [1,2,4,8]

💡 Note: Perfect chain where each number divides the next: 1|2, 2|4, 4|8. All pairs are divisible.

Example 3 — Single Element

$ Input: nums = [5]

› Output: [5]

💡 Note: With only one element, it forms a valid divisible subset by itself.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 2 × 10⁹
All the integers in nums are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Array of distinct positive integers

Process

Find subset where every pair is divisible

Output

Largest valid divisible subset

Key Takeaway

🎯 Key Insight: Divisibility has transitivity property - if a|b and b|c, then a|c, allowing efficient DP solution

Asked in

G Google 25 f Facebook 20 a Amazon 15

Brief HTML summary: The key insight is leveraging the transitivity property of divisibility. If a|b and b|c, then a|c. Best approach is sort + dynamic programming which builds the longest divisible subsequence efficiently. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsets	O(n × 2^n)	O(n)	Generate all possible subsets and check if each forms a divisible subset
Sort + Dynamic Programming	O(n²)	O(n)	Sort array first, then use DP to build longest divisible subsequence

Brute Force - Try All Subsets — Algorithm Steps

Generate all possible subsets using bit manipulation
For each subset, check if all pairs are divisible
Return the largest valid subset

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^n possible combinations using bit masks

Validate Each

Check if every pair in subset satisfies divisibility

Find Maximum

Return the largest valid divisible subset

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    int* bestSubset = (int*)malloc(numsSize * sizeof(int));
    *returnSize = 0;
    
    // Try all possible subsets using bit manipulation
    for (int mask = 1; mask < (1 << numsSize); mask++) {
        int subset[20];
        int subsetSize = 0;
        
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                subset[subsetSize++] = nums[i];
            }
        }
        
        // Check if this subset is valid (all pairs divisible)
        int valid = 1;
        for (int i = 0; i < subsetSize && valid; i++) {
            for (int j = i + 1; j < subsetSize; j++) {
                if (subset[i] % subset[j] != 0 && subset[j] % subset[i] != 0) {
                    valid = 0;
                    break;
                }
            }
        }
        
        // Update best if this is larger and valid
        if (valid && subsetSize > *returnSize) {
            for (int i = 0; i < subsetSize; i++) {
                bestSubset[i] = subset[i];
            }
            *returnSize = subsetSize;
        }
    }
    
    return bestSubset;
}

int main() {
    int nums[20];
    int numsSize = 0;
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2^n)

Generate 2^n subsets, each taking O(n²) time to validate pairs

⚠ Quadratic Growth

Space Complexity

O(n)

Store current subset and result array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

982 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler