Permutations Solution

2 May 2021

Statement

( The original statement can be found here )
A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 1. Given n, construct a beautiful permutation if such a permutation exists.

Input
The only input line contains an integer n.

Output
Print a beautiful permutation of integers 1,2,…,n. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

Constraints
1 ≤ n ≤ 10^6
Time limit : 1.00s
Memory limit : 512MB


Example 1

Input :
5
Output :
4 2 5 3 1


Example 2

Input :
3
Output :
NO SOLUTION

Solution

We are asked to find a permutation of length N such that no adjacent elements have an absolute difference of 1. This type of problem is classical and can be solved using constructive algorithms. Such algorithms rely on finding some type of construction that holds some property for some specific input.
One possible way to solve this is to separate the even numbers from the odd numbers. Since the absolute difference between any adjacent even numbers is always two (the same goes for odd numbers) then the initial property holds right? At first, this seems to be the case but we need to be careful with corner cases such as N=4 where [ 1 3 2 4 ] is an invalid permutation but [ 2 4 1 3 ] is a valid one. It is easy to see that for N=2 and N=3 there are no possible solutions and our intuition tells us that the approach described above works for any N>3 if we are careful enough to put the even numbers first.

#include <bits/stdc++.h>
using namespace std;

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

    int value = 2;

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

    while(value <= n) {
      cout << value << " ";
      value += 2;
    }

    value = 1;

    while(value <= n) {
      cout << value << " ";
      value += 2;
    }

    return 0;
}

This algorithm is really efficient since it runs in a time complexity of O(N) and space complexity of O(1).