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
You made some decent points there. I checked on the net to learn more about the issue and found most people will go along with your views on this web site.
Oh my goodness! Impressive article dude! Thank you, However I am experiencing problems with your RSS. I don’t understand why I am unable to subscribe to it. Is there anyone else getting the same RSS issues? Anyone that knows the solution will you kindly respond? Thanx.
Pretty! This has been a really wonderful article. Thanks for providing this information.
There is definately a great deal to learn about this issue. I love all of the points you’ve made.
Pretty! This was a really wonderful post. Thanks for supplying these details.