Coding

Largest Divisible Subset

Asked at

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array nums of positive integers, the task is to find the largest subset such that every pair (a, b) of elements in the subset satisfies a % b == 0 or b % a == 0.

Return the subset in any order. If there are multiple solutions, return any one of them.

Note: As there can be multiple correct answers, the compiler returns 1 if the answer is valid, else 0.

Input: nums = [3, 5, 10, 20] Output: [5, 10, 20] Explanation: The subset [5, 10, 20] satisfies the divisibility condition: 10 % 5 == 0 and 20 % 10 == 0.

Input: nums = [16, 8, 2, 4, 32] Output: [2, 4, 8, 16, 32] Explanation: The entire array forms a divisible subset since 32 % 16 == 0, 16 % 8 == 0, and so on.

Input: nums = [7, 14, 28, 3]

1 <= nums.length <= 103
1 <= nums[i] <= 106

cpp

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int> nums) {
      
    }
};

java

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        
    }
}

python

class Solution:
    def largestDivisibleSubset(self, nums):

javascript

class Solution {
    largestDivisibleSubset(nums) {
   
    }
}

csharp

public class Solution
{
    public List<int> LargestDivisibleSubset(int[] nums)
    {
        
    }
}

func largestDivisibleSubset(nums []int) []int {
	
}

Stuck? Show a way to structure it+

01Sort ascending so divisors come first
02Initialize every length to one and predecessor to itself
03Relax from earlier divisible values
04Backtrack predecessors from the best endpoint

Reference answer

Start by restating the input contract for Largest Divisible Subset and testing the smallest boundary case before choosing the algorithm. Sort positive numbers ascending, then compute the longest valid subset ending at each index. If nums[i] is divisible by nums[j], it can extend j's subset. Store a predecessor pointer whenever a better length is found, then backtrack from the best endpoint. Explain the invariant while coding, then show how each update preserves it. The pairwise DP checks take O(n^2) time after sorting and the lengths plus predecessor arrays use O(n) space. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

Why does sorting make the DP valid?
Tests: correctness reasoning
How could you tie-break among equal subsets?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question