Ctrl K

Цепочка кратных

Средняя
Дан набор различных положительных целых чисел numbers. Выберите из него как можно больше чисел так, чтобы в любой паре выбранных одно делилось на другое без остатка. Верните выбранные числа в любом порядке. Гарантируется, что самый большой такой набор ровно один.
Пример 1
numbers=[9, 2, 18, 6, 4] → [18, 6, 2]

2, 6 и 18: 6 делится на 2, 18 — на 6 и на 2. Четырёх чисел, где каждая пара делится одно на другое, здесь не набрать.

Пример 2
numbers=[3, 24, 6, 12] → [24, 12, 6, 3]

Подходят все четыре: каждое следующее по величине кратно предыдущему.

Пример 3
numbers=[7] → [7]
Ограничения
  • 1 ≤ len(numbers) ≤ 1000
  • 1 ≤ numbers[i] ≤ 2 · 10⁹
  • Все числа различны
  • Самый большой подходящий набор единственный
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиНаборы без заданной разницы СредняяНаборы без заданного разрыва СредняяКрайние значения маленьких групп СредняяНаибольшее число, кратное трём СложнаяПостаматы вдоль дороги Сложная
загружаем Python…
Вход
numbers=[9, 2, 18, 6, 4]
Ожидается
[18, 6, 2]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 64 теста на сервере, включая скрытые.