[Solution] MEX vs DIFF Codeforces Solution | Codeforces Problem Solution 2022

[Solution] MEX vs DIFF Codeforces Solution | Codeforces Problem Solution 2022

E. MEX vs DIFF

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array 𝑎$a$ of 𝑛$n$ non-negative integers. In one operation you can change any number in the array to any other non-negative integer.

Let's define the cost of the array as DIFF(𝑎)−MEX(𝑎)$\mathrm{DIFF}(a)-\mathrm{MEX}(a)$, where MEX$\mathrm{MEX}$ of a set of non-negative integers is the smallest non-negative integer not present in the set, and DIFF$\mathrm{DIFF}$ is the number of different numbers in the array.

For example, MEX({1,2,3})=0$\mathrm{MEX}(\{1,2,3\})=0$, MEX({0,1,2,4,5})=3$\mathrm{MEX}(\{0,1,2,4,5\})=3$.

Solution Click Below:-  CLICK HERE

You should find the minimal cost of the array 𝑎$a$ if you are allowed to make at most 𝑘$k$ operations.

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of test cases. Description of the test cases follows.

Digit Minimization Codeforces Solution

Z mod X = C Codeforces Solution

Column Swapping Codeforces Solution

Traps Codeforces Solution

MEX vs DIFF Codeforces Solution

Diverse Segments Codeforces Solution

Euclid Guess Codeforces Solution

Hard Cut Codeforces Solution

The first line of each test case contains two integers 𝑛$n$ and 𝑘$k$ (1≤𝑛≤105$1\le n\le {10}^5$, 0≤𝑘≤105$0\le k\le {10}^5$) — the length of the array 𝑎$a$ and the number of operations that you are allowed to make.

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (0≤𝑎𝑖≤109$0\le a_i\le {10}^9$) — the elements of the array 𝑎$a$.

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 105${10}^5$.

Output

For each test case output a single integer — minimal cost that it is possible to get making at most 𝑘$k$ operations.