MEX Game 1 (Codeforces 1943A)
Tags: Greedy, games

Alice and Bob play yet another game on an array $$$a$$$ of size $$$n$$$. Alice starts with an empty array $$$c$$$. Both players take turns playing, with Alice starting first.On Alice's turn, she picks one element from $$$a$$$, appends that element to $$$c$$$, and then deletes it from $$$a$$$.On Bob's turn, he picks one element from $$$a$$$, and then deletes it from $$$a$$$. The game ends when the array $$$a$$$ is empty. Game's score is defined to be the MEX$$$^\dagger$$$ of $$$c$$$. Alice wants to maximize the score while Bob wants to minimize it. Find game's final score if both players play optimally.$$$^\dagger$$$ The $$$\operatorname{MEX}$$$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:   The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.  The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.  The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not. 

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, find game's score if both players play optimally.

Note: In the first test case, a possible game with a score of $$$2$$$ is as follows:   Alice chooses the element $$$1$$$. After this move, $$$a=[0,0,1]$$$ and $$$c=[1]$$$.  Bob chooses the element $$$0$$$. After this move, $$$a=[0,1]$$$ and $$$c=[1]$$$.  Alice chooses the element $$$0$$$. After this move, $$$a=[1]$$$ and $$$c=[1,0]$$$.  Bob chooses the element $$$1$$$. After this move, $$$a=[\,]$$$ and $$$c=[1,0]$$$. At the end, $$$c=[1,0]$$$, which has a MEX of $$$2$$$. Note that this is an example game and does not necessarily represent the optimal strategy for both players.

Sample Inputs:
3
4
0 0 1 1
4
0 1 2 3
2
1 1

Sample Outputs:
2
1
0

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = sorted(map(int, input().split()))
    li = [0] * n
    for i in a:
        li[i] += 1
    x = 0
    ans = n
    for i in range(n):
        if li[i] == 0:
            ans = i
            break
        if li[i] == 1:
            x += 1
        if x == 2:
            ans = i
            break
    print(ans)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = sorted(map(int, input().split()))
    li = [0] * n
    for i in a:
        li[i] += 1
    x = 0
    ans = n
    for i in range(n):
        if li[i] == 0:
            ans = i
            break
        if li[i] == 1:
            x += 1
        if x == 2:
            ans = i
            break
    print(ans)

Solution (Python):
def solve():
    n = int(input())
    f = [0] * (n + 1)
    a = list(map(int, input().split()))
    for i in range(n):
        f[a[i]] += 1
    c = 0
    for i in range(0, n + 1):
        c += f[i] == 1
        if c == 2 or f[i] == 0:
            print(i)
            break

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()