Ctrl K

Наибольшее число, кратное трём

Сложная
У вас есть набор карточек, на каждой написана одна цифра; они даны в массиве cards. Выложите в ряд некоторые из карточек (можно все, можно не все, в любом порядке) так, чтобы получилось как можно большее число, делящееся на 3. Верните это число строкой: оно может оказаться очень длинным. В записи не должно быть лишних ведущих нулей — например, из одних нулей получается просто "0". Если ни одного подходящего числа сложить нельзя, верните пустую строку.
Пример 1
cards=[4, 7, 2] → '72'

Сумма всех цифр 13 не делится на 3. Если убрать 4 или 7, сумма станет кратна трём; лучше убрать 4 и сложить 72.

Пример 2
cards=[5, 0, 0, 8, 1] → '8100'

Сумма 14, остаток 2. Убираем самую маленькую цифру с остатком 2 — это 5, остаются 8, 1, 0, 0 и число 8100.

Пример 3
cards=[0, 0, 0] → '0'

Из одних нулей получается только 0 — без лишних ведущих нулей.

Ограничения
  • 1 ≤ len(cards) ≤ 10⁴
  • 0 ≤ cards[i] ≤ 9
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЛучший порядок дегустационного сета СложнаяПостаматы вдоль дороги СложнаяСуммарная сила отрядов СложнаяРастущие группы без повторов СложнаяПереключения по рёбрам дерева Сложная
загружаем Python…
Вход
cards=[4, 7, 2]
Ожидается
'72'

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