 # PERMCREATE - Editorial

Author: Jeevan Jyot Singh
Tester: Hriday
Editorialist: Nishank Suresh

1323

None

# PROBLEM:

Given N, construct a permutation of \{1, 2, \ldots, N\} such that any two adjacent elements differ by 2, or say that no such permutation exists.

# EXPLANATION:

If N = 2 or N = 3, no valid permutation exists. Otherwise, a required permutation always exists.

There are many constructions, one simple one is as follows:

• First, print all the even numbers till N. That is, 2, 4, 6, \ldots with the last element being either N-1 (if N is odd) or N (if N is even).
• Then, print all the odd numbers.

For example, if N = 7 this results in [2, 4, 6, 1, 3, 5, 7] and if N = 10 this results in [2, 4, 6, 8, 10, 1, 3, 5, 7, 9].

Adjacent odd numbers and adjacent even numbers differ by exactly 2, and as long as N \geq 4, 1 will be adjacent to an number that is at least 4, so this construction works for all N\geq 4.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
if n <= 3:
print(-1)
continue
print(*range(2, n+1, 2), *range(1, n+1, 2))

1 Like