Нагадаємо: масиву — це найменше невід'ємне ціле число, якого в ньому немає. Умова \mathrm{mex} \le k означає, що серед чисел 0, 1, \ldots, k хоча б одного немає в масиві.
Звідси одразу випливає структура розв'язку. Оберемо якесь число v \in [0, k] і видалимо всі його входження — тоді зникне з масиву, а отже \mathrm{mex} \le v \le k. Видаляти щось іще не потрібно, а видалити менше не вийде: доки всі числа від до присутні, буде більшим за .
Отже, вартість вибору дорівнює кількості входжень , і відповідь — мінімум по всіх кандидатах:
Розв'язок: одним проходом порахувати для кожного значення (їх лише десять, бо 0 \le a_i \le 9), а потім узяти мінімум по від до .
Окремі випадки обробляються автоматично. Якщо якесь v \le k у масиві вже відсутнє, його лічильник дорівнює нулю, і відповідь — нуль. Якщо k = 10, то кандидат v = 10 теж дає нуль, бо елементи не перевищують .
Складність — \mathcal{O}(n + k).