Permutations

Permutations
CSES easy

A permutation of the numbers \(1, 2, \ldots, n\) is beautiful if no two adjacent elements differ by \(1\).

Construct a beautiful permutation, or report that none exists.

Constraints:

  • \(1 \le n \le 10^6\)

Input:

  • One line: integer \(n\).

Output:

  • A beautiful permutation of \(1, 2, \ldots, n\). If there are several, print any of them. If there is none, print NO SOLUTION.

Examples:

Input:

5

Output:

4 2 5 3 1

Input:

3

Output:

NO SOLUTION
Solution

We start with small \(n\), as the lesson on constructive algorithms suggests:

  • \(n = 1\): the permutation \(1\) has no adjacent elements, so it is beautiful.
  • \(n = 2\) and \(n = 3\): we can check all orders; in each of them \(2\) is next to \(1\) or to \(3\). There is no solution.
  • \(n = 4\): \(2\ 4\ 1\ 3\) is beautiful.

The idea of \(2\ 4\ 1\ 3\) works for every \(n \ge 4\): first print all even numbers in increasing order, then all odd numbers in increasing order.

  • Two adjacent even numbers differ by \(2\), and so do two adjacent odd numbers.
  • At the border, the largest even number is next to \(1\). It is at least \(4\), so the difference is at least \(3\).

For \(n = 1\) the same code prints no even numbers and then the number \(1\), which is also correct.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n == 2 || n == 3) {
        cout << "NO SOLUTION\n";
        return 0;
    }

    // first all even numbers, then all odd numbers
    for (int i = 2; i <= n; i += 2) {
        cout << i << ' ';
    }
    for (int i = 1; i <= n; i += 2) {
        cout << i << ' ';
    }
    cout << "\n";
}