Paprika and Permutation (Codeforces 1617C)
Tags: Greedy, binary search

Paprika loves permutations. She has an array $$$a_1, a_2, \dots, a_n$$$. She wants to make the array a permutation of integers $$$1$$$ to $$$n$$$.In order to achieve this goal, she can perform operations on the array. In each operation she can choose two integers $$$i$$$ ($$$1 \le i \le n$$$) and $$$x$$$ ($$$x > 0$$$), then perform $$$a_i := a_i \bmod x$$$ (that is, replace $$$a_i$$$ by the remainder of $$$a_i$$$ divided by $$$x$$$). In different operations, the chosen $$$i$$$ and $$$x$$$ can be different.Determine the minimum number of operations needed to make the array a permutation of integers $$$1$$$ to $$$n$$$. If it is impossible, output $$$-1$$$.A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

Output: For each test case, output the minimum number of operations needed to make the array a permutation of integers $$$1$$$ to $$$n$$$, or $$$-1$$$ if it is impossible.

Note: For the first test, the only possible sequence of operations which minimizes the number of operations is:   Choose $$$i=2$$$, $$$x=5$$$. Perform $$$a_2 := a_2 \bmod 5 = 2$$$. For the second test, it is impossible to obtain a permutation of integers from $$$1$$$ to $$$n$$$.

Sample Inputs:
4
2
1 7
3
1 5 4
4
12345678 87654321 20211218 23571113
9
1 2 3 4 18 19 5 6 7

Sample Outputs:
1
-1
4
2

Solution (Python):
import sys
import bisect
import math
from collections import deque
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 7

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    arr = []
    visited = [False] * (1 + n)
    for i in a:
        if i <= n and (not visited[i]):
            visited[i] = True
        else:
            arr.append(i)
    arr.sort()
    j = 0
    for i in range(1, n + 1):
        if not visited[i]:
            if arr[j] < 2 * i + 1:
                return -1
            j += 1
    return j
if __name__ == '__main__':
    t = 1
    t = int(input())
    for _ in range(t):
        print(solve())

Solution (Python):
def replace_bool(list_a, index, p_list):
    list_a[p_list[index]] = True
    return list_a

def solve():
    n = int(input())
    main = [int(x) for x in input().split()]
    (a, bigger) = ([False] * (n + 1), [])
    [replace_bool(a, i, main) if main[i] <= n and a[main[i]] is False else bigger.append(main[i]) for i in range(n)]
    bigger = sorted(bigger)
    counter = 0
    for i in range(1, n + 1):
        if not a[i]:
            if (bigger[counter] - 1) // 2 >= i:
                counter += 1
            else:
                return -1
    return counter
try:
    print(*[solve() for _ in range(int(input()))], sep='\n')
except Exception as error:
    print(error)

Solution (Python):
import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def paprika_and_permutation(n, a):
    total = 0
    p = set(range(1, n + 1))
    a_ = []
    for ai in a:
        if ai in p:
            p.remove(ai)
        else:
            a_ += [ai]
    for (pi, ai) in zip(sorted(p), a_):
        if ai == pi:
            continue
        if pi * 2 >= ai:
            return -1
        total += 1
    return total
for _ in range(int(input())):
    n = int(input())
    a = sorted(map(int, input().split()))
    sys.stdout.write(f'{paprika_and_permutation(n, a)}\n')