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.
Solution
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.
License
Copyright 2016-present George Cushen.
Released under the MIT license.
