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.

HackerRank Absolute Permutation Solution
HackerRank Absolute Permutation Solution

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

Ezoicreport this adTask

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 1based 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 spaceseparated 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

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

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

Sharing Is Caring

Leave a Comment

Ezoicreport this ad