 # PERMUTATION - Editorial

Authors: notsoloud
Testers: iceknight1093, mexomerf
Editorialist: iceknight1093

1197

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)


how can time complexity be O(n) (as mentioned in the editorial) if you are sorting the array?

1 Like

The constraint A_i \leq 1000 allows you to sort the array using a frequency array of size 1000, taking \mathcal{O}(N + 1000) per test case (which is just \mathcal{O}(N) in terms of complexity)

1 Like