Absolute Permutation HackerRank Solution in C, C++, Java, Python

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 i in permutation P using 1-based indexing.

P is considered to be an absolute permutation if |posi[i]-i]=k holds true for every i belongs to [1,n].

Given n and k, print the lexicographically smallest absolute permutation . If no absolute permutation exists, print -1.

For example, let n=4 giving us an array pos=[1,2,3,4]. If we use 1 based indexing, create a permutation where every |pos[i]-1| = k. If k=2, we could rearrange them to [3,4,1,2]:

pos[i]	i	|Difference|
3	1	2
4	2	2
1	3	2
2	4	2

Function Description

Complete the absolutePermutation function in the editor below. It should return an integer that represents the smallest lexicographically smallest permutation, -1 or if there is none.

absolutePermutation has the following parameter(s):

n: the upper bound of natural numbers to consider, inclusive
k: the integer difference between each element and its index

Input Format

The first line contains an integer t, the number of test cases.
Each of the next t lines contains 2 space-separated integers, n and k.

Output Format

On a new line for each test case, print the lexicographically smallest absolute permutation. If no absolute permutation exists, print -1.

Sample Input

3
2 1
3 0
3 2

Sample Output

2 1
1 2 3
-1

Absolute Permutation HackerRank 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 HackerRank Solution in C++

#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 HackerRank 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 HackerRank 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 HackerRank Solution in C#

using System;
using System.Linq;

class Solution
{
    static void Main(String[] args)
    {
        var cases = int.Parse(Console.ReadLine());
        for (var c = 0; c < cases; ++c)
        {
            DoCase();
        }
    }

    private static void DoCase()
    {
        var t = Console.ReadLine().Split(' ');
        var n = int.Parse(t[0]);
        var k = int.Parse(t[1]);
        if (k == 0)
        {
            Console.WriteLine(string.Join(" ", Enumerable.Range(1, n)));
            return;
        }
        if (n % (2 * k) != 0)
        {
            Console.WriteLine(-1);
            return;
        }
        var blocks = n / 2 / k;
        var r = Enumerable.Range(1, n).ToArray();
        for (var i = 0; i < blocks; ++i)
        {
            var offset1 = 2 * k * i;
            var offset2 = 2 * k * i + k;
            for (var j = 0; j < k; ++j, ++offset1, ++offset2)
            {
                var v = r[offset1];
                r[offset1] = r[offset2];
                r[offset2] = v;
            }
        }
        Console.WriteLine(string.Join(" ", r));
    }
}

Attempt Absolute Permutation HackerRank Challenge

Link –¬†https://www.hackerrank.com/challenges/absolute-permutation/

Next HackerRank Challenge Solution 

Link –¬†https://exploringbits.com/the-bomberman-game-hackerrank-solution/

 

Leave a Comment