Borland & Owned
Borland
Привет, Властелин, готов бросить вызов безумной алгоритмической задаче, где важна и скорость, и точность? Слышал про новый челлендж, который превращает классическую задачу в гонку на время.
Owned
Ну давай, попробуй. Если быстро, я превращу это в спринт. Посмотрим, сможешь ли ты угнаться, или тебе просто будет очередной мой трофей.
Borland
Ладно, вот тебе задачка: дан массив целых чисел, нужно найти длину самого длинного непрерывного подмассива, сумма которого делится на заданное число k. Подвох в том, что нужно решить её за линейное время и с постоянным объёмом дополнительной памяти, без хэш-таблиц и дополнительных массивов. Готов нырнуть?
Owned
Конечно, давай сделаем это одним проходом и минимизируем использование памяти. Заведи небольшой вспомогательный массив размером *k*, который будет хранить индекс первого появления каждого остатка. Инициализируй его нулями, установи остаток 0 на индексе -1, чтобы учитывать префиксы, которые уже делятся нацело. Проходи по списку, добавляя текущее число к текущей сумме и беря остаток от деления на *k*. Если этот остаток уже встречался, значит, у тебя есть подмассив от индекса предыдущего появления остатка + 1 до текущего индекса, сумма которого кратна *k*. Обнови максимальную длину, если она больше текущей. Если остаток новый, запиши его индекс. Это займет O(n) времени и O(k) памяти – что практически постоянно, если *k* ограничено условиями задачи. Попробуй и посмотрим, кто первым получит самую длинную последовательность!
Borland
Звучит неплохо, сейчас разложу всё по шагам. Сначала создаёшь массив длины *k*, заполненный единицами –1. Устанавливаем нулевой элемент в –1, потому что пустой префикс считается делимым. Потом проходишь по списку, поддерживая текущую сумму и её остаток от деления на *k*. Как только встречаешь остаток, для которого уже есть сохранённый индекс, срез между этим сохранённым индексом плюс один и текущим индексом – это потенциальный подмассив. Отслеживаешь его длину и запоминаешь максимальную. Если остаток новый, сохраняешь текущий индекс. Так ты обрабатываешь каждый элемент только один раз, используешь O(k) памяти (постоянный объём, если *k* фиксировано) и решаешь задачу за линейное время. Хочешь, чтобы я сейчас напишу реальный код на твоём любимом языке?
Owned
Давай код, нечего тут тянуть. Я его пробегу быстрее, чем ты напечатаешь. Посмотрим, успеешь ли ты!