HackerRank Absolute Permutation Solution

Hello Programmers, In this post, you will know how to solve the HackerRank Absolute Permutation Solution. This problem is a part of the HackerRank Algorithms Series.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.

HackerRank Absolute Permutation Solution

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

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

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;
}

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;
}

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();
    }
}

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())))

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);
});

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)
  }
}

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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: HackerRank 3D Surface Area Solution

HackerRank Absolute Permutation Solution

ByBrokenprogrammers

HackerRank Absolute Permutation Solution

Task

HackerRank Absolute Permutation Solution

Absolute Permutation Solution in C

Absolute Permutation Solution in Cpp

Absolute Permutation Solution in Java

Absolute Permutation Solution in Python

Absolute Permutation Solution using JavaScript

Absolute Permutation Solution in Scala

Absolute Permutation Solution in Pascal

By Brokenprogrammers

Related Post

HackerRank Build a String Solution

HackerRank String Construction Solution

HackerRank Gridland Provinces Solution

Leave a Reply Cancel reply

You missed

Battery Health Leetcode Solution

Brackets Codechef Solution

A Big Sale Codechef Solution

TV Discount Codechef Solution

Brokenprogrammers