#4032 | Longest Subarray With at Most K Distinct Prime Factors

Topics: prime factorization, 2 pointers

Problem Statement:

You are given an integer array numsconsisting of positive integers and an integer k. The prime factor set of a subarray is the union of the distinct prime factors of all its elements. Return the length of the longest subarray whose prime factor set contains at most k distinct prime factors. If no such subarray exists, return 0.

Input: nums = [7,6,10,12,11], k = 3
Output: 3
Explanation: longest subarray -> [6, 10, 12]
* 6: {2, 3}
* 10: {2, 5}
* 12: {2, 3}

Union set of prime factors: {2, 3, 5} and number of sets is at most K.

🔗 Link: https://leetcode.com/problems/longest-subarray-with-at-most-k-distinct-prime-factors/

#POTD #LeetCode

«Ой да көп, уайым да көп – ойлай берсең,
Ой да жоқ, уайым да жоқ – ойнай берсең».

© Мұхтар Әуезов

Mo's algorithm is an efficient offline query-processing technique based on Square Root (sqrt) Decomposition. It is designed to answer multiple range queries [L, R] on a static array in an optimized order, achieving an overall time complexity ofO((N + Q) * sqrt(N)), where N is the number of elements and Q is the number of queries.

Popularized by Chinese competitive programmer Mo Tao, the algorithm allows you to solve range query problems that cannot easily be solved using standard segment trees or Fenwick trees (such as finding the number of distinct elements or the most frequent element in a range).

CP Algo Article: https://cp-algorithms.com/data_structures/sqrt_decomposition.html
CF Blog about Mo's algorithm: https://codeforces.com/blog/entry/81716
LC Problem to practice: https://leetcode.com/problems/valid-k-unique-subarrays-i

#algorithms #notes

На прошлом ивенте у меня спрашивали про следующий митап. Скидываю информацию:

Приглашаем на AI DevDay! Meetup на тему AI.

Вас ждут три доклада от приглашенных спикеров:

Азамат Рыскулбеков (Инженер по ML-моделям, Freedom AI Labs)
Тема: Как маскировать персональные данные и сделать это в 50 раз быстрее — путь от большой LLM для поиска персональных данных до гибридного пайплайна из regex, NER, роутинга и LLM fallback.

Шынгыс Шонаев (тимлид команды разработки, Freedom AI Labs)
Тема: Mechanical quality gates для качественного AI-кодинга — почему не нужны большинство скиллов и правил в AGENTS.md, и как заменить спеки тестами.

Алекс Рассудихин (Frontend Developer, Kolesa, ex-Freedom Health)
Тема: Как организовать AI-инструкции и масштабировать их — о хаосе при работе над несколькими проектами с нейронками, двух решениях для порядка в папке .claude, и полезных инструментах для работы с нейронками.

📅 Когда: 23 сентября (среда)
🕐 Во сколько: 18:30 (перекус и нетворкинг) и до 21:00
Где: Алматы, БЦ "Almaty Towers", Байзакова 280, вход со стороны платной парковки, офис Choco

Митап бесплатный, но количество мест ограничено. Регистрация обязательна.

#Astana Google на DevFest Astana! 🌟💪

Эксперты с Google летят. Это возможность:
1️⃣ Увидеть, как мыслят и работают инженеры одной из самых инновационных компаний мира.
2️⃣ Узнать о самых свежих инженерных практиках в Cloud Native и ИИ напрямую от источника.
3️⃣ Лично пообщаться с Ramesh Chander и Alper Sarı во время нетворкинга.

Такой нетворкинг случается раз в году. Не упусти шанс вдохновиться и прокачать свой нетворкинг-скилл на Alem.ai.

📅 17 сентября, Астана.
🔴 Мест мало, а желающих много. Будь в числе первых!

🎟️ Мероприятие бесплатное, но нужна регистрация. Хватай свой билет по ссылке https://forms.gle/cTt32nE1SS6L1YVU6

Важная информация по входу:
Вход на мероприятие осуществляется через мобильное приложение Astana Hub.
Участникам необходимо заранее скачать приложение и при входе отсканировать QR-код, размещённый на телевизоре.
Если приложению требуется обновление, рекомендуем сделать это заранее, чтобы пройти регистрацию без задержек. @devs_kz

QAZDATATHON 2026

~ это ежегодный республиканский конкурс по работе с большими данными, который организует Бюро национальной статистики Агентства по стратегическому планированию и реформам Республики Казахстан.

Кто может участвовать?
Обучающиеся ВУЗ-ов, исследователи в области социальных наук, а также лица, работающие с данными, являющиеся гражданами государств – участников Содружества Независимых Государств (СНГ) в возрасте до 35 лет (включительно)

Состав команды:
от 2 до 5 человек с пониманием экономической теории, знаниями в области социологии, политологии и других социальных наук, а также навыками работы со статистическими приложениями, языками программирования и BI-инструментами.

Цели:

~ Поиск новых подходов к решению социально-экономических и методологических задач с помощью данных.
~ Развитие культуры принятия решений на основе данных (data-driven) среди молодежи и специалистов.
~ Создание инновационных проектов для улучшения государственной политики и сфер занятости, экономики и социальных наук.

🔗 Link: https://datathon.stat.gov.kz

#datathon #competition

Codeforces Round 1120 (Div. 1, Div. 2) starts in ~2 hours. Please, join by the link https://codeforces.com/contests/2262,2263

Starts at 19:35 (GMT+5, Almaty tz)

Happy International Programmer's Day!
-> 256th day of the year!
-> 2^8 = 256;
-> 13 September, 2026;

Congratulations! 💫