Chain of Multiples

Medium

You get a collection of distinct positive integers numbers. Pick as many of them as you can so that, in every pair of picked numbers, one divides the other evenly. Return the picked numbers in any order. The input is guaranteed to have exactly one largest such selection.

Example 1

numbers=[9, 2, 18, 6, 4] → [18, 6, 2]

2, 6 and 18: 6 is a multiple of 2, and 18 is a multiple of both 6 and 2. No four numbers here pair up that way.

Example 2

numbers=[3, 24, 6, 12] → [24, 12, 6, 3]

All four fit: each one, in increasing order, is a multiple of the one before.

Example 3

numbers=[7] → [7]

Constraints

1 ≤ len(numbers) ≤ 1000
1 ≤ numbers[i] ≤ 2 · 10⁹
All numbers are distinct
Exactly one largest valid selection exists

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Dynamic Programming Sorting

Similar problems

Picks Without a Fixed Gap Medium Sets Without a Fixed Gap Medium Extremes of Small Groups Medium Biggest Number Divisible by Three Hard Parcel Lockers Along a Road Hard

Input

numbers=[9, 2, 18, 6, 4]

Expected

[18, 6, 2]

Run checks the first 3 tests in your browser. Submit checks all 64 tests on the server, hidden ones included.