In this post, we will solve HackerRank Absolute Permutation Problem Solution.
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 & 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.
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
Absolute Permutation C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int t, n, k;
scanf("%d",&t);
while(t--) {
scanf("%d %d",&n,&k);
if(k!=0 && n%(2*k)!=0) {
printf("-1");
} else {
for(int i=1,c=0;i<=n;i++) {
if(c>=0) {
printf("%d",i+k);
c++;
if(c==k) c=-k;
} else {
printf("%d",i-k);
c++;
}
if(i<n) printf(" ");
}
}
printf("\n");
}
return 0;
}Absolute Permutation C++ Solution
#include <bits/stdc++.h>
using namespace std;
#ifdef WIN32
#define I64 "%I64d"
#else
#define I64 "%lld"
#endif
typedef long long ll;
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int(s.size()))
#define fname "a"
#define MAXN 1000001
int n, k;
int a[MAXN];
inline void solve()
{
scanf("%d%d", &n, &k);
if (!k) {
for (int i = 0; i < n; ++i)
printf("%d%c", i + 1, " \n"[i + 1 == n]);
return;
}
if (n % (k + k) > 0) {
puts("-1");
return;
}
for (int i = 0; i < n; i += k + k)
for (int j = 0; j < k; ++j) {
a[i + j] = i + j + k;
a[i + j + k] = i + j;
}
for (int i = 0; i < n; ++i)
printf("%d%c", a[i] + 1, " \n"[i + 1 == n]);
}
int main()
{
#ifdef LOCAL
freopen(fname".in", "r", stdin);
freopen(fname".out", "w", stdout);
#endif
int tt;
scanf("%d", &tt);
for (int t = 0; t < tt; ++t)
solve();
return 0;
}Absolute Permutation C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
int t = Convert.ToInt32(Console.ReadLine());
for(int a0 = 0; a0 < t; a0++){
string[] tokens_n = Console.ReadLine().Split(' ');
int n = Convert.ToInt32(tokens_n[0]);
int k = Convert.ToInt32(tokens_n[1]);
int[] r = new int[n+1];
bool[] placed = new bool[n+1];
for (int i=1; i<=(n/2)+1; i++)
{
int tp = i-k;
if ((tp > 0) && (tp <= n) && (r[tp] == 0) && (!placed[i]))
{
r[tp] = i;
placed[i] = true;
}
tp = (n-i+1)+k;
if ((tp > 0) && (tp <= n) && (r[tp] == 0) && (!placed[n-i+1]))
{
r[tp] = (n-i+1);
placed[n-i+1] = true;
}
tp = i+k;
if ((tp > 0) && (tp <= n) && (r[tp] == 0) && (!placed[i]))
{
r[tp] = i;
placed[i] = true;
}
tp = (n-i+1)-k;
if ((tp > 0) && (tp <= n) && (r[tp] == 0) && (!placed[n-i+1]))
{
r[tp] = (n-i+1);
placed[n-i+1] = true;
}
}
if (placed.Count(e => e) != n)
{
Console.WriteLine("-1");
} else {
int[] rt = new int[n];
Array.Copy(r, 1, rt, 0, n);
Console.WriteLine(String.Join(" ", rt));
}
}
}
}Absolute Permutation Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'absolutePermutation' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER k
*/
public static List<Integer> absolutePermutation(int n, int k) {
if (k > n / 2) {
return List.of(-1);
}
Integer[] res = new Integer[n];
Set<Integer> indexesLeft = Stream.iterate(1, i -> i <= n, i -> i + 1).collect(Collectors.toSet());
for (int i = n; i > 0; i--) {
int index = i + k;
if (!indexesLeft.remove(index)) {
index = i - k;
if (!indexesLeft.remove(index)) {
return List.of(-1);
}
}
res[index - 1] = i;
}
return Arrays.asList(res);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, t).forEach(tItr -> {
try {
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int k = Integer.parseInt(firstMultipleInput[1]);
List<Integer> result = Result.absolutePermutation(n, k);
bufferedWriter.write(
result.stream()
.map(Object::toString)
.collect(joining(" "))
+ "\n"
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}Absolute Permutation JavaScript Solution
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
function main() {
var t = parseInt(readLine());
for(var a0 = 0; a0 < t; a0++){
var n_temp = readLine().split(' ');
var n = parseInt(n_temp[0]);
var k = parseInt(n_temp[1]);
if (k > 0 && n%(2*k) != 0) {
console.log('-1');
continue;
}
var temp = [];
for (var i = 1; i <= n; i++) {
if (k == 0) {
temp[i] = i;
} else if (i < k) {
temp[i] = i+k;
} else if (i > n-k) {
temp[i] = i-k;
} else if (Math.ceil(i/k)%2 == 0) {
temp[i] = i-k;
} else {
temp[i] = i+k;
}
}
temp = temp.slice(1);
temp = temp.join(' ');
console.log(temp);
}
}Absolute Permutation Python Solution
def perm(n,k):
if k == 0:
for i in range(n):
yield i+1
return
elif n % (2*k) != 0:
yield -1
return
else:
for i in range(1,n+1):
if ((i-1) // k) % 2 == 0:
yield i+k
else:
yield i-k
T = int(input().strip())
for ti in range(T):
N,K = (int(x) for x in input().strip().split())
o = ' '.join([str(x) for x in perm(N,K)])
print(o)Other Solutions
