Lesson 9

Programming problem. Given a permutation of integers from \(0\) to \(n\), determine its parity.

• Input format.  The first line contains the integer \(n\) (\(2 \le n \le 100\)). The next line contains \(n+1\) integers separated by spaces — the elements of the permutation. It is guaranteed that the line defines a valid permutation, that is, \(\pi[i] \ne \pi[j]\) for \(i \ne j\) and \(0 \le \pi[i] \le n\).


• Output format.  Output one number: \(0\) if the permutation is even, and \(1\) if it is odd.

Since the number of elements is not too large here, it is perfectly fine to implement an algorithm that finds a sequence of transpositions and checks its parity. A naive implementation of this method has running time \(O(n^{2})\): at each of about \(n\) iterations, one needs a linear scan to find the current element. Interestingly, this problem can also be solved in time \(O(n\log n)\) (using an efficient sorting algorithm) and even in time \(O(n)\) (to do this, one either decomposes the given permutation into cycles; another possibility is to keep the permutation and its inverse while sorting it).

3
3 0 2 1

0