Subset Mex (Codeforces 1406A)
Tags: Greedy, implementation

Given a set of integers (it can contain equal elements).You have to split it into two subsets $$$A$$$ and $$$B$$$ (both of them can contain equal elements or be empty). You have to maximize the value of $$$mex(A)+mex(B)$$$.Here $$$mex$$$ of a set denotes the smallest non-negative integer that doesn't exist in the set. For example:   $$$mex(\{1,4,0,2,2,1\})=3$$$  $$$mex(\{3,3,2,1,3,0,0\})=4$$$  $$$mex(\varnothing)=0$$$ ($$$mex$$$ for empty set) The set is splitted into two subsets $$$A$$$ and $$$B$$$ if for any integer number $$$x$$$ the number of occurrences of $$$x$$$ into this set is equal to the sum of the number of occurrences of $$$x$$$ into $$$A$$$ and the number of occurrences of $$$x$$$ into $$$B$$$.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t\leq 100$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$1\leq n\leq 100$$$) — the size of the set.The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\dots a_n$$$ ($$$0\leq a_i\leq 100$$$) — the numbers in the set.

Output: For each test case, print the maximum value of $$$mex(A)+mex(B)$$$.

Note: In the first test case, $$$A=\left\{0,1,2\right\},B=\left\{0,1,5\right\}$$$ is a possible choice.In the second test case, $$$A=\left\{0,1,2\right\},B=\varnothing$$$ is a possible choice.In the third test case, $$$A=\left\{0,1,2\right\},B=\left\{0\right\}$$$ is a possible choice.In the fourth test case, $$$A=\left\{1,3,5\right\},B=\left\{2,4,6\right\}$$$ is a possible choice.

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

Sample Outputs:
5
3
4
0

Solution (Python):
t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    arr = [int(a) for a in input().split()]
    count = [0 for i in range(101)]
    for a in arr:
        count[a] += 1
    ans = 0
    for i in range(101):
        if count[i] == 0:
            ans += i
            break
    for i in range(101):
        if count[i] <= 1:
            ans += i
            break
    print(ans)

Solution (Python):
for s in [*open(0)][2::2]:
    a = [0] * 101
    for x in s.split():
        a[int(x)] += 1
    i = a.index(0)
    a[i] = 1
    print(i + a.index(1))

Solution (Python):
test_num = int(input())
for i in range(test_num):
    test_lenth = int(input())
    test = list((int(x) for x in input().split()))
    A = []
    B = []
    for x in test:
        if x not in A:
            A.append(x)
        else:
            B.append(x)
    a = min(A)
    if len(B) != 0:
        b = min(B)
    else:
        b = 0
    if 0 < a:
        a = 0
    else:
        while a in A:
            a += 1
    if 0 < b:
        b = 0
    elif len(B) != 0:
        while b in B:
            b += 1
    sum = a + b
    print(sum)