Divisible Permutation

The condition says $|p_i-p_{i+1}|$ must be divisible by $i$. Instead of trying to use random multiples of $i$, use the most boring valid multiple: $i$ itself. If we can construct a permutation with

$$|p_i-p_{i+1}|=i$$

for every $1 \le i \le n-1$, then the divisibility condition is done. No drama.

Now build a helper permutation $a$ whose consecutive differences go the other way:

$$n-1,n-2,n-3,\ldots,1.$$

There is a very simple construction:

$$a = [1,n,2,n-1,3,n-2,\ldots].$$

That means we repeatedly take the smallest unused number, then the largest unused number.

Why does this work? Look at adjacent terms:

• Between $1$ and $n$, the difference is $n-1$.
• Between $n$ and $2$, the difference is $n-2$.
• Between $2$ and $n-1$, the difference is $n-3$.
• And so on.

More formally, for every adjacent pair in $a$ at position $j$,

$$|a_j-a_{j+1}|=n-j.$$

So the differences of $a$ are exactly

$$n-1,n-2,\ldots,1.$$

But we need the differences to be $1,2,\ldots,n-1$ in that order. So just reverse $a$ and call the result $p$.

If

$$p_i = a_{n-i+1},$$

then the difference between $p_i$ and $p_{i+1}$ corresponds to the difference between $a_{n-i+1}$ and $a_{n-i}$, which is exactly $i$:

$$|p_i-p_{i+1}| = i.$$

Since $i$ is divisible by $i$, every condition holds.

The array is definitely a permutation because the construction uses every number from $1$ to $n$ exactly once: one from the left end, one from the right end, until nothing is left.

Edge cases are harmless. For $n=2$, the construction gives either $[2,1]$ after reversing, and the only required difference is $1$, which works. Odd $n$ just leaves one middle number at the end of the helper array before reversing; still fine.

Complexity per test case is $O(n)$ time and $O(n)$ memory. With $n \le 100$, this is basically free, but still clean.