MEX rose

To make $\operatorname{MEX}(a)=k$, the array must satisfy exactly this:

• Every value $0,1,2,\dots,k-1$ appears at least once.
• The value $k$ appears zero times.

Everything bigger than $k$ is irrelevant. It can sit there doing nothing. Very productive lifestyle.

What must be fixed?

Let:

• $missing$ = how many numbers in $[0,k-1]$ do not appear in the array.
• $countK$ = how many elements are equal to $k$.

Each missing number below $k$ must be created somehow, so we need at least $missing$ operations.

Each occurrence of $k$ must be removed, because if $k$ appears, then the MEX cannot be $k$. So we also need at least $countK$ operations.

Therefore the answer is at least:

$$\max(missing, countK)$$

Now we need to show this lower bound is actually reachable.

Why the max is enough

Suppose a value below $k$ is missing and there is an occurrence of $k$. Change that $k$ into the missing value.

That single operation fixes both problems:

• One bad $k$ disappears.
• One missing required value appears.

So we pair as many missing values with occurrences of $k$ as possible.

If there are extra $k$'s left afterward, change them to anything harmless, like $n$ or some value greater than $k$.

If there are extra missing values left afterward, change some non-essential elements into them. This is always possible because the array has length $n$ and $k \le n$; after keeping one copy of every already-present required value, there are enough other positions to modify.

So the exact minimum is:

$$\boxed{\max(missing, countK)}$$

Edge cases

If $k=0$, there are no required smaller values. We only need to remove all zeroes, so the answer is just the number of zeroes.

If $k=n$, then all values $0$ through $n-1$ must appear and $n$ must not appear. The same formula still works perfectly.

Algorithm

For each test case:

1. Count frequencies of all values from $0$ to $n$.
2. Count how many values $i$ in $[0,k-1]$ have frequency $0$.
3. Let $countK = freq[k]$.
4. Print $\max(missing, countK)$.

Complexity is $O(n)$ per test case, and $O(\sum n)$ overall.