MEX Game 1 (Codeforces 1944C)
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):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, a) = (readInt(), readList())
    cnt = [0] * n
    for v in a:
        cnt[v] += 1
    flag = 0
    for i in range(n):
        if cnt[i] == 0:
            return i
        elif cnt[i] == 1:
            if flag:
                return i
            else:
                flag = 1
    return n
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, a) = (readInt(), readList())
    cnt = [0] * n
    for v in a:
        cnt[v] += 1
    flag = 0
    for i in range(n):
        if cnt[i] == 0:
            return i
        elif cnt[i] == 1:
            if flag:
                return i
            else:
                flag = 1
    return n
for _ in range(int(input())):
    print(solve())

Solution (Python):
from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
T = int(input().split()[0])
for _ in range(T):
    n = int(input().split()[0])
    board = [0] * n
    for v in map(int, input().split()):
        board[v] += 1
        pass
    score = 0
    for (i, v) in enumerate(board):
        if v == 0:
            score = i
            break
        elif v == 1:
            if score == 0:
                score = 1
            elif score == 1:
                score = i
                break
        pass
    print(str(score) + '\n')
    pass