HackerRank Absolute Permutation Solution

In this post, we will solve HackerRank Absolute Permutation Problem Solution.

We define P to be a permutation of the first ŉ 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

HackerRank Absolute Permutation Problem Solution

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)