FOR FREE YEAR SOLVED

We define P to be a permutation of the first n natural numbers in the range [1, n], let pos[i] denote the value at position i in permutation P using 1 – based indexing.

P is considered to be an absolute permutation if |pos[i] – i| = k holds true for every i ∈ [1, n]

Given n and k, print the lexicographically smallest absolute permutation P. If no absolute permutation exists, print – 1. For example, let n = 4 giving us an array pos = [1, 2, 3, 4]. If we use 1 based indexing, create a permutation where every |pos[i] – i| = k. If k = 2, we could rearrange them to [3, 4, 1, 2]

Let’s understand the question, for a given range n i.e. first n natural numbers, we have to permute the numbers in such a way that the pos[i] – i where ‘i’ is the index should be equal to k. if such permutation not possible then return – 1 else return the array formed using the permutated values.

One thing is that, if the length of the array is odd and the difference is not 0, i.e. k ≠ 0 then there is no such possible permutation exists.

Example

n = 3                   k = 0

1 2 3 

Output Permutation: 1 2 3

Example

n = 3                   k = 1

O/P no such permutation exist.

n = 3 → 1 2 3

We cannot form any permutation such that the difference at pos[i] – i = k

Step 1: Declare an array

Step 2: Run a loop n time to insert values from 0 to n in the array

Step 3: If the difference is 0, i.e. n = 0 then return the array from position 1 to last as we need the permutation for first n                              numbers.

Step 4: If the length is odd, difference is ≠ 0 then return – 1

Step 5: Run a loop

                            for i = 1 to n – k + 1

                                  if arr[i] == (arr[i + k] – k)

                                            then swap arr[i], arr[i + k]

                                  else if absolute value of (i – arr[i]) != k

                                            return – 1

Now, let us understand what we are doing. 

For each position we are checking whether the value at arr[i] == (arr[i + k] – k) (i.e. value at position i + (difference)) – k

If same we are swapping.

For example

n = 2                   k = 1

0 1 2

Now for i = 1 to n – k + 1 i.e. 2

arr[1] == arr[2] – 1

∴ arr[1], arr[2] is swapped

In the else part we are checking whether the difference between position and value = k or not if no then return – 1

Step 6: Now run a loop

                         for i = n – k + 1 to n

                                    if the absolute difference of (i – arr[i]) != k

                                                   return -1

Here after swapping at Step 5 we are checking the difference from the position n – k + 1 to n, if the difference between index number and value at that index ≠ k then return – 1 i.e. no such permutation exists.

Step 7: Return the array from index 1 to last arr[1: ]