Absolute Permutation – HackerRank Solution

In this post, we will solve Absolute Permutation HackerRank Solution. This problem (Absolute Permutation) is a part of HackerRank Problem Solving series.

Task

We define P to be a permutation of the first n natural numbers in the range [1, n]. Let  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.

Example

n = 4
k = 2

Create an array of elements from 1 to n, pos = [1. 2, 3, 4]. Using 1 based indexing, create a permutation where every [pos[i] – i] = k. It can be rearranged to [3, 4, 1, 2] so that all of the absolute differences equal k = 2:

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

Function Description

Complete the absolutePermutation function in the editor below.

absolutePermutation has the following parameter(s):

• int n: the upper bound of natural numbers to consider, inclusive
• int k: the absolute difference between each element’s value and its index

Returns

• int[n]: the lexicographically smallest permutation, or [-1] if there is none

Input Format

The first line contains an integer t, the number of queries.
Each of the next t lines contains 2 space-separated integers, n and k.

Constraints

• 1 <= t <= 10
• 1 <= n <= 10⁵
• 0 <= k < n

Sample Input

STDIN   Function
-----   --------
3       t = 3 (number of queries)
2 1     n = 2, k = 1
3 0     n = 3, k = 0
3 2     n = 3, k = 2

Sample Output

2 1
1 2 3
-1

Solution – Absolute Permutation – HackerRank Solution

C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

int main() {
    int t,n,k;
    std::cin >> t;

    std::vector<bool> used;
    while (t-- > 0) {
        std::cin >> n >> k;

        used = std::vector<bool>(n, false);

        if (k == 0){
            for (int i = 1; i <= n; i++)
                std::cout << i << " ";
            std::cout << std::endl;
            continue; /* moves on to next test case! */
        } else if (n % (2*k) != 0) {
            std::cout << -1 << std::endl;
            continue;
        }

        for (int i = 1,j; i <= n; i += 2*k) {
            for (j = i; j < i+k; j++)
                std::cout << j+k << " ";
            for (j = i+k; j < i+2*k; j++)
                std::cout << j-k << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

Python

import sys

def max_permutation(n, k):
    #array = [x for x in range(1, n+1)]
    out = []
    switch = k
    if k == 0:
        return [x for x in range(1, n+1)]
    
    if n % (2*k) != 0:
        return [-1]
        
    for pos in range(1, n + 1):
        out.append(pos + switch)
        
        if pos % k == 0:
            switch *= -1
            
    return out
        
        

t = int(input().strip())
for a0 in range(t):
    n, k = input().strip().split(' ')
    n, k = [int(n),int(k)]
    
    print(" ".join(list(map(str, max_permutation(n, k)))))

Java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            int n = in.nextInt();
            int k = in.nextInt();

            if (k == 0) {
                for (int i = 1; i <= n; i++) {
                    System.out.print(i + " ");
                }
                System.out.println();
            } else if (n % 2 == 0 && n % (2 * k) == 0) {
                int blocks = n / k;
                int currentNumber = k;
                for (int i = 0; i < blocks; i++) {
                    for (int j = 0; j < k; j++) {
                        currentNumber++;
                        System.out.print(currentNumber + " ");

                    }
                    if (i % 2 != 0) {
                        currentNumber = currentNumber + (2 * k);
                    } else {
                        currentNumber = currentNumber - (2 * k);
                    }
                }
                System.out.println();
            } else {
                System.out.println(-1);
            }

        }
    }                
}

Note: This problem (Absolute Permutation) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.