[CSES] Permutations

2021-06-23

1 minute read

Algorithm

cses

Repetitions

Task:

A permutation of integers $1,2,\ldots,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,\ldots,n$. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

Constraints

$1 \le n \le 10^6$

Example 1

Input:
5

Output:
4 2 5 3 1

Example 2

Input:
3

Output:
NO SOLUTION

Solutions:

Intuition:

Any valid solution is accepted, so get the easiest one. It's the successive odd or even number series. For example if $n$ is $5$ then first part's gonna be odd number series [1,3,5] and the rest part is [2,4]. Combining it, we get [1,3,5,2,4]. Let's do the same for bigger $n$ . And don't forget the edge cases, this approach seems to be wrong with $n=4$, we have only one valid arrangement for 4 : [3,1,4,2]. and whenever $n < 4$, we return "NO SOLUTION".

Implementation:

 1n=int(input())
 2path=[]
 3if n==1:
 4    print("1")
 5elif n<4:
 6    print("NO SOLUTION")
 7elif n==4:
 8    print("3 1 4 2")
 9else:
10    res=""
11    # odd number series
12    for i in range(1,n+1,2):
13        res+=(str(i)+" ")
14
15    # even number series
16    for i in range(2,n+1,2):
17        res+=(str(i)+" ")
18
19    print(res.strip())
20

Analysis:

Time complexity: O(N).

Space complexity: O(1).