Hello Programmers, In this post, you will learn how to solve HackerRank Absolute Permutation Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t straight away look for the solutions, first try to solve the problems by yourself. If you find any difficulty after trying several times, then look for the solutions. We are going to solve the HackerRank Algorithms problems using C, CPP, JAVA, PYTHON, JavaScript & SCALA Programming Languages.
HackerRank Absolute Permutation
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 <= 105
- 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
Explanation
Test Case 0:
Test Case 1:
Test Case 2:
No absolute permutation exists, so we print -1 on a new line.
HackerRank Absolute Permutation Solution
HackerRank Absolute Permutation Solution in C
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int i,j,n,t,k;
scanf("%d",&t);
while(t>0){
t--;
scanf("%d %d",&n,&k);
if(k==0){
for(i=0;i<n;i++)printf("%d ",i+1);
printf("\n");
continue;
}
if((n%(2*k))!=0){
printf("-1\n");
continue;
}
for(i=0;i<(n/(2*k));i++){
for(j=0;j<k;j++)printf("%d ",((2*k*i)+k+j+1));
for(j=0;j<k;j++)printf("%d ",((2*k*i)+j+1));
}
printf("\n");
}
return 0;
}HackerRank Absolute Permutation Solution in Cpp
#include <bits/stdc++.h>
using namespace std;
int N, K;
int A[100000];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &N, &K);
memset(A, -1, sizeof A);
bool bad=false;
for(int i=0; i<N; i++)
{
if(i-K>=0 && A[i-K]==-1)
A[i-K]=i;
else if(i+K<N && A[i+K]==-1)
A[i+K]=i;
else
bad=true;
}
if(bad)
printf("-1\n");
else
{
for(int i=0; i<N; i++)
printf("%d ", A[i]+1);
printf("\n");
}
}
return 0;
}HackerRank Absolute Permutation Solution in Java
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int tc = scanner.nextInt();
for (int t = 0; t < tc; ++t) {
int n = scanner.nextInt();
int k = scanner.nextInt();
print(solve(n, k));
}
}
private static int[] solve(int n, int k) {
if (k > 0 && n % (2 * k) != 0) {
return null;
}
int[] res = new int[n];
int shift = k;
for (int i = 1; i <= n; ++i) {
res[i - 1] = i + shift;
if (k > 0 && i % k == 0) {
shift *= -1;
}
}
return res;
}
private static void print(int[] a) {
if (a == null) {
System.out.println(-1);
return;
}
for (int i = 0; i < a.length; ++i) {
if (i > 0) {
System.out.print(" ");
}
System.out.print(a[i]);
}
System.out.println();
}
}HackerRank Absolute Permutation Solution in Python
def solve(N,K):
if K == 0: return range(1,1+N)
if N%(2*K): return [-1]
base = range(K+1,2*K+1) + range(1,1+K)
ans = []
Q = N/(2*K)
for q in xrange( Q ):
for i in base:
ans.append( q*2*K + i )
return ans
rr = raw_input
rrI = lambda: int(rr())
rrM = lambda: map(int,rr().split())
for _ in xrange(rrI()):
print " ".join(map(str, solve(*rrM())))HackerRank Absolute Permutation Solution using JavaScript
function processData(input) {
var lines = input.split(/\n/);
var tests = lines.shift();
for (var line of lines) {
var info = line.split(/ /).map(Number);
var n = info.shift();
var k = info.shift();
var possibilities = [];
var bag = {};
var i = 1;
var failed = false;
while (i <= n) {
var range = [i - k, k + i];
var found = false;
loop: for (var j = 0; j < range.length; j++) {
var choice = range[j];
if (bag[choice] == undefined && choice > 0 && choice <= n) {
bag[choice] = 1;
possibilities.push(choice);
found = true;
break loop;
}
}
if (! found) {
failed = true;
break;
}
i++;
}
process.stdout.write((failed ? -1 : possibilities.join(' ')) + "\n")
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});HackerRank Absolute Permutation Solution in Scala
import collection.mutable.LinkedHashSet
object Solution extends App {
val lines = io.Source.stdin.getLines()
for (tc <- 0 until lines.next.toInt) {
val nums = lines.next.split(' ').map(_.toInt)
val (n, k) = (nums.head, nums.last)
val used = LinkedHashSet[Int]()
for (i <- 1 to n) {
if (ok(i - k)) used += (i - k)
else if (ok(i + k)) used += (i + k)
else used.clear()
}
println( if (used.size < n) "-1" else used.mkString(" ") )
def ok(x: Int) = x > 0 && x <= n && !used.contains(x)
}
}HackerRank Absolute Permutation Solution in Pascal
uses math;
var n,p,k,i,w,t:longint;
begin
readln(t);
for w:=1 to t do
begin
read(n,k);
if k=0 then
begin
for i:=1 to n do
write(i,' ');
writeln();
end
else
if n mod (2*k)<>0 then writeln(-1) else
begin
p:=0;
while(p*k<n) do
begin
for i:=p*k+k+1 to (p+2)*k do
write(i,' ');
for i:=p*k+1 to p*k+k do
write(i,' ');
inc(p,2);
end;
writeln();
end;
end;
end.Disclaimer: This problem (Absolute Permutation) is generated by HackerRank but the solution is provided by Chase2learn. This tutorial is only for Educational and Learning purposes.