Largest Divisible Subset Problem

Largest Divisible Subset Problem — ExecCode Hard DSA Practice

Solve the Largest Divisible Subset problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Description Imagine you're solving Largest Divisible Subset in a real system where you must be correct and efficient. Problem Given a list of distinct positive integers, find the largest subset such that for every pair (Si, Sj) in the subset, either Si % Sj == 0 or Sj % Si == 0. If there are multiple valid subsets of the same maximum size, any one of them is acceptable. Input Format A single line containing a JSON-style array of integers (e.g. [1,2,3]). Output Format A JSON-style array representing one largest divisible subset (order of elements in the output does not matter as long as the subset is valid). Constraints All input integers are positive and distinct. The input array length is at least 1.

Examples

Input [1,2,3]; Output [1,2]. Input [1,2,4,8]; Output [1,2,4,8]

Constraints

1 <= nums.length <= 1000

Practice Largest Divisible Subset free on ExecCode. Browse DSA problems, topic map, and placement guides.