Odd or even permutation?

A challenging puzzle interlacing mathematics and algorithms

Problem Statement

Given $N$ and $K$, generate the sequence $a_i := K \cdot i \,\, (\mathrm{mod }\,\, N)$. Let $M$ be the number of inversions1 of the sequence $(a_0, a_1, \dots, a_{j-1})$ where $j$ is the smallest positive index such that $a_j = 0$. Determine if $M$ is odd or even. The challenge here is to design an algorithm that solves this problem quickly.

Example: if $N = 5$ and $K = 3$, then the sequence is $(0, 3, 1, 4, 2)$. Its number of inversions $M$ is $3$, which is odd.

Before reading on, I invite you to try a few more examples to get a feel for this problem. See if you can spot a pattern.


Click to reveal solution If you are well trained in elementary number theory, you may have sensed that this problem "smells" number theoretic. Otherwise, you might be surprised to know that this problem is related to quadratic reciprocity! The complete solution can be found here (external link here).

[1] The number of inversions of a sequence of numbers is the minimum number of adjacent swaps required to sort the numbers in non-decreasing order.


Copyright 2016-present George Cushen.

Released under the MIT license.

Kam Chuen (Alex) Tung
Kam Chuen (Alex) Tung
PhD Candidate in Computer Science