Ctrl K

Цепочка с одинаковым остатком сумм

Средняя
Дан массив положительных чисел values и число modulus. Выберите цепочку — несколько элементов в исходном порядке (не обязательно подряд) — так, чтобы суммы всех пар соседей в цепочке давали один и тот же остаток при делении на modulus. Верните длину самой длинной такой цепочки. Любые два элемента образуют подходящую цепочку.
Пример 1
values=[3, 7, 1, 5, 9], modulus=4 → 3

Цепочка 1, 5, 9: суммы соседей 6 и 14, обе дают остаток 2 при делении на 4.

Пример 2
values=[2, 5, 8, 11, 4], modulus=3 → 4

Все числа, кроме 4, дают остаток 2 по модулю 3, значит, все суммы соседей в цепочке 2, 5, 8, 11 дают остаток 1.

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

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