ОПТИМИЗАЦИЯ ЗАДАЧИ ПО НАХОЖДЕНИЮ САМОГО ДЛИННОГО ПОДМАССИВА, КОЛИЧЕСТВО ПРОСТЫХ ДЕЛИТЕЛЕЙ У КОТОРОГО МЕНЬШЕ ЗАДАННОГО ЧИСЛА К

SOLUTION TO THE PROBLEM OF FINDING THE LONGEST SUBARRAIL, WHICH HAS LESS THAN A GIVEN NUMBER OF PRIME DIVIDERS K

Gumin Mikhail Mikhailovich

4rd year student of the Department of «Information Systems of Digital Economy», Russian University of Transport,

Russia, Moscow

Morozova Vera Ivanovna

Scientific supervisor, candidate of Sciences in Economics, associate professor, Russian University of Transport,

Russia, Moscow

АННОТАЦИЯ

В статье рассматривается решение задачи о поиске самого длинного подмассива, множество уникальных простых множителей которого не более переданного числа к, взятой с сайта LeetCode [2]. Для оптимизации вместо полного перебора применяются такие техники оптимизации как: «скользящее окно» и модифицированное решето Эратосфена для быстрого нахождения наименьшего простого делителя чисел. Дополнительно используется такие инструменты как кэширование разложений и хеш-таблица для подсчёта простых множителей в текущем окне. Такой подход позволяет снизить сложность до O(NlogM), близкой к линейной, и делает алгоритм эффективным даже при больших входных данных.

ABSTRACT

This article examines the problem - sourced from LeetCode of finding the longest subarray where the number of unique prime factors does not exceed a given value k. To optimize the solution, techniques such as the «sliding window» approach and a modified Sieve of Eratosthenes (for rapidly identifying the smallest prime divisor) are employed instead of a brute-force search. Additionally, the algorithm utilizes prime factorization caching and a hash table to track prime factors within the current window. This approach reduces the complexity to O(Nlog M) approaching linear time making the algorithm efficient even for large input datasets.

Ключевые слова: оптимизация, алгоритм, скользящее окно, решето Эратосфена, Big(O).

Keywords: optimization, algorithm, sliding window, sieve of Eratosthenes, Big(O).

В данной статье будет представлен разбор решения задачи с сайта LeetCode [2]. Условие задачи следующее – Дан целочисленный массив nums, состоящий из положительных целых чисел, и целое число k. Множество простых множителей подмассива – это объединение множеств различных простых множителей всех его элементов. Верните длину самого длинного подмассива, множество простых множителей которого содержит не более k различных простых множителей. Если такого подмассива не существует, верните 0.

Все решение по своей сути заключается в переборе всех возможных подмассивов, с сохранением максимальной длины за время перебора. Однако простой линейный поиск (или полный перебор) не будет эффективным. Ибо в таком случае согласно нотации Big O время работы программы будет соответствовать O(n²) (квадратичная сложность). Это означает, что время работы алгоритма растет пропорционально квадрату от размера входных данных. К примеру длине коллекции равной 1, скорость выполнения будет 1² = 1, при 10 скорость будет равна 10² = 100, при 1000 скорость выполнения будет 1000² = 1_000_000, а при 100_000 скорость выполнения будет 10_000² = 10_000_000_000. Можно увидеть насколько сильно увеличивается время работы нашего решения, при каждом последующем увеличение размера входных данных.

Для оптимизации решения воспользуемся такой техникой решения, как sliding window[4]. Sliding window или же скользящее окно – это популярный метод оптимизации в программирование, при котором вместо полного пересчета структуры на каждом шаге поддерживается небольшой фрагмент данных («окно»), который сдвигается вдоль последовательности, за счет использования двух указателей, характеризующий границы этого окна.

Также не стоит упускать из внимания второе условие, а именно «множество простых множителей». Первым дело решим вопрос получения всех простых множителей конкретного числа. Одни из вариантов – полный перебор всех чисел, определение среди них простых и проверка на то, являются ли они множителем переданного числа или нет. Такой подход объясняется основной теоремой арифметики [3], которая утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причем единственным способом. Полный перебор всех чисел для проверки простоты и делимости неэффективен при больших размерах входных данных. Вместо этого можно заранее вычислить наименьший простой делитель (далее НПД) для всех чисел начиная с 2 и до самого большого значения в массиве. Для этого воспользуемся модифицированным алгоритмом «решето Эратосфена» [1].

Идея алгоритма «решето Эратосфена» заключается в том, что для каждого натурального числа сохраняется его НПД. Изначально для всех чисел полагаем НПД равным самому значению числа. Далее проходимся по числам начиная с 2. Если текущее число является простым (то есть его НПД равен самому числу), то для всех кратных ему чисел, начиная с его квадрата, обновляем НПД, заменяя ему его значение на найденное простое число, но только при условии, если оно ещё не было изменено. Просчет начиная с квадрата числа обуславливается тем, что до квадрата числа одним из множителей точно будет меньшее простое число. Таким образом, после завершения работы решета, для любого составного числа можно мгновенно узнать его наименьший простой делитель.

Используя массив НПД, разложение числа на простые множители выполняется очень быстро. Пока число больше 1, берём его НПД из сформированного нами ранее списка, добавляем этот множитель в список, проверяя его на наличие в коллекции для того чтобы исключить дубликаты, делим число на этот делитель и повторяем. В результате получаем список всех различных простых множителей исходного числа. Такой подход требует времени, пропорционального количеству простых множителей, которое для чисел до 100_000 (ограничение из самой задачи) обычно не превышает 6-7 и потому очень эффективен.

Для ускорения работы алгоритма имеет смысл кэшировать результаты разложения на простые множители для всех уникальных чисел, встречающихся во входных данных, чтобы не проводить повторный разбор того же числа.

Теперь можно приступать к поиску самого длинного подмассива, удовлетворяющего условию.

Инициализируем два указателя: левая граница окна(left) и правая граница окна (right) [5]. Также будем поддерживать хеш-таблицу, или как их еще называют – словарь, который хранит для каждого простого множителя количество его вхождений среди чисел текущего окна. Количество ключей, следовательно, равно уникальному числу простых множителей в окне.

Начиная с пустого окна, left = 0 и right = 0, постепенно расширяем окно, двигая правый указатель вправо. При добавлении нового элемента в окно, следуем такой логике:

1. Получаем список его простых множителей или из метода, или из хеш-таблицы вычисленных ранее числе, если было реализовано кэширование;
2. Для каждого множителя увеличиваем его счётчик в словаре, для новых проставляем количество равным единице;
3. Если счётчик множителя был равен нулю или множитель отсутствовал, значит этот множитель впервые появился в окне, и значит увеличиваем общий счётчик уникальных простых множителей.

После добавления элемента может оказаться, что общее число различных простых множителей превысило допустимое значение k. В этом случае начинаем сдвигать левую границу окна вправо, удаляя элементы из начала окна, до тех пор, пока условие снова не будет выполнено. При удалении элемента:

1. Получаем его простые множители;
2. Для каждого множителя уменьшаем его счётчик в словаре;
3. Сдвигаем левую границу окна, пока количество уникальных простых множителей больше допустимого значения k. Если число вхождений множителя становится равным нулю, значит этот множитель больше не встречается в окне, и тогда уменьшаем общий счётчик различных множителей.

После сдвига левой границы окна, вычисляем его длину и проверяем больше ли она нашего локального максимума или нет. Если больше, обновляем значения максимума на длину текущего окна.

Важно отметить, что каждый элемент добавляется в окно не более одного раза и удаляется не более одного раза, поэтому суммарное количество операций с элементами линейно относительно размера массива, количество операций равно размеру входных данных O(n). Обработка простых множителей одного элемента занимает по сути константное время, так как число множителей невелико.

Также из условия задачи следует, что минимальное число, встречающееся в массиве, это 2. Оттого поведение алгоритма при встрече 1 не рассматривалось. Однако в случае если во входных данных может присутствовать значение равное 1, в таком случае нужно обнулить окно, указав значение для левой границы как текущий индекс + 1, поскольку текущее значение равно 1 и его нельзя разложить на простые множители.

Предложенный в данной статье алгоритм решения задачи основывается на двух методах оптимизации: улучшенный алгоритм «решето Эратосфена» через квадрат числа для быстрого нахождения НПД и скользящее окно для эффективного перебора элементов массива.

За счет используемых численных методов удается избежать квадратичной сложности при переборе подмассивов, из-за чего итоговая временная сложность решения соответствует O(N log(M)), близкая к линейной сложности, что делает алгоритм пригодным для обработки еще больших входных данных.

Список литературы:

1. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 4th ed. Cambridge: MIT Press, 2022. - 1312 p.
2. Longest Subarray With at Most K Distinct Prime Factors // LeetCode. [электронный ресурс] - Режим доступа. - URL: https://leetcode.com/problems/longest-subarray-with-at-most-k-distinct-prime-factors (дата обращения 28.10.2026).
3. Riesel H. Prime Numbers and Computer Methods for Factorization. 2nd ed. Boston: Birkhäuser, 1994. - 464 p.
4. Crochemore M., Hancart C., Lecroq T. Algorithms on Strings. Cambridge: Cambridge University Press, 2007. - 392 p.
5. Heineman G.T., Pollice G., Selkow S. Algorithms in a Nutshell. 2nd ed. Sebastopol: O’Reilly Media, 2016. - 948 p.