PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: notsoloud
Testers: iceknight1093, mexomerf
Editorialist: iceknight1093
DIFFICULTY:
1197
PREREQUISITES:
None
PROBLEM:
You have an array A. In one move, you can increase some A_i by 1.
Find the minimum cost to make A into a permutation of [1, 2, \ldots, N] or claim that this is impossible.
EXPLANATION:
Ideally, we’d like to turn the smallest element of A into 1, the second smallest into 2, \ldots, the largest into N.
So let’s do exactly this!
Sort the array A, so that A_1 \leq A_2 \leq \ldots \leq A_N.
Now, we want to turn A_i into i, which needs i - A_i moves.
If A_i \gt i for any index i, then the answer is -1 since we can’t turn A_i into i, we aren’t allowed to decrease elements.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
ans = sum(i+1 - a[i] for i in range(n))
for i in range(n):
if a[i] > i+1: ans = -1
print(ans)