MEX vs DIFF solution codeforces

by

MEX vs DIFF solution codeforces

You are given an array aa of nn 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(a)−MEX(a)DIFF⁡(a)−MEX⁡(a), where MEXMEX of a set of non-negative integers is the smallest non-negative integer not present in the set, and DIFFDIFF is the number of different numbers in the array.

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

You should find the minimal cost of the array aa if you are allowed to make at most kk operations.

Input

MEX vs DIFF solution codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers nn and kk (1≤n≤1051≤n≤105, 0≤k≤1050≤k≤105) — the length of the array aa and the number of operations that you are allowed to make.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1090≤ai≤109) — the elements of the array aa.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

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

Example

MEX vs DIFF solution codeforces

input

Copy
4
4 1
3 0 1 2
4 1
0 2 4 5
7 2
4 13 0 0 13 1337 1000000000
6 2
1 2 8 0 0 0
output

Copy
0
1
2
0
Note

MEX vs DIFF solution codeforces

In the first test case no operations are needed to minimize the value of DIFF−MEXDIFF−MEX.

In the second test case it is possible to replace 55 by 11. After that the array aa is [0,2,4,1][0,2,4,1], DIFF=4DIFF=4, MEX=MEX({0,1,2,4})=3MEX=MEX⁡({0,1,2,4})=3, so the answer is 11.

In the third test case one possible array aa is [4,13,0,0,13,1,2][4,13,0,0,13,1,2], DIFF=5DIFF=5, MEX=3MEX=3.

In the fourth test case one possible array aa is [1,2,3,0,0,0][1,2,3,0,0,0].

SOLUTION

“Click here“

MEX vs DIFF solution codeforces is one of the most asked coding question. This question is repeated in almost every company paper and if you are ready to crack the interviews and the question papers then you must check our website on daily purpose so that you can get the answer of the latest question “MEX vs DIFF solution codeforces”.

Leave a Comment