PERMUTATION - Editorial

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)

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