Absolute Permutation

We define P to be a permutation of the first n natural numbers in the range . Let  denote the value at the position i in permutation P using -based indexing.

 is considered to be an absolute permutation if  holds true for every .

Given  and k, print the lexicographically smallest absolute permutation P. If no absolute permutation exists, print -1.

Example

Create an array of elements from  to , . Using  based indexing, create a permutation where every . It can be rearranged to  so that all of the absolute differences equal :

pos[i]  i   |pos[i] - i|
  3     1        2
  4     2        2
  1     3        2
  2     4        2

Example:

Input:  n = 3, k = 0
Output: 1 2 3

Approach

C++

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

vector<int> absolutePermutation(int n, int k)
{
    vector<int> res;
    if (k == 0)
    {
        for (int i = 1; i <= n; i++)
            res.push_back(i);
        return res;
    }
    else if (n % (2 * k) != 0 || 2 * k > n)
        return {-1};
    for (int i = 0; i < n; i++)
    {
        if ((i / k) % 2 == 0)
            res.push_back(i + 1 + k);
        else
            res.push_back(i + 1 - k);
    }
    return res;
}

int main()
{

    int n = 3, k = 0;

    vector<int> result = absolutePermutation(n, k);

    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i];

        if (i != result.size() - 1)
        {
            cout << " ";
        }
    }

    cout << "\n";

    return 0;
}