Permutations
Construct a permutation of 1 through n where neighboring values never differ by exactly 1.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Reorder the numbers \(1, 2, \ldots, n\) so that every pair of neighboring values differs by something other than \(1\). If no such order exists, report that immediately.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
The small cases are the only impossible ones:
\(n = 1\) is already valid
\(n = 2\) and \(n = 3\) have no solution
For \(n \ge 4\), a simple construction works: print all even numbers first, then all odd numbers.
Why does that help?
inside the even block, consecutive numbers differ by \(2\)
inside the odd block, consecutive numbers also differ by \(2\)
the only boundary is from the largest even number to the smallest odd number, and for \(n \ge 4\) that gap is never \(1\)
So the entire permutation is valid.
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(n)\)
Memory: \(O(1)\) besides the output itself
C++ Solution
The exact repository source used for this solution page.
#include <iostream>
int main() {
int n;
std::cin >> n;
if (n == 1) {
std::cout << 1 << '\n';
return 0;
}
if (n == 2 || n == 3) {
std::cout << "NO SOLUTION\n";
return 0;
}
bool first = true;
for (int value = 2; value <= n; value += 2) {
if (!first) {
std::cout << ' ';
}
std::cout << value;
first = false;
}
for (int value = 1; value <= n; value += 2) {
if (!first) {
std::cout << ' ';
}
std::cout << value;
first = false;
}
std::cout << '\n';
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
Do not overcomplicate the construction. The even-then-odd ordering is the intended simple pattern.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.