Algorithm


Problem Name: Data Structures -Find the permutation

Problem Link: https://www.hackerrank.com/challenges/find-the-permutation/problem?isFullScreen=true

In this HackerRank in Data Structures - Find the permutation solutions,

In this HackerRank Find the Permutation problem solution we are given a permutation pi of integers from 1 to n. we need to generate a lexicographically sorted list of all permutations of length n having a maximal distance between all permutations of the same length. Print the lexicographically kth permutation.

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include<stdio.h>
#include<stdlib.h>
static const unsigned long long one = 1;
static unsigned long long * solution;
unsigned long long n, k;
void solve2I(unsigned long long r)
{
    unsigned long long sf = n - 2 * r - 1;
    unsigned long long sb = n - 1;
    unsigned long long s2 = 2;
    for( unsigned long long i = 0 ; i  <  r ; ++i )
    {
        unsigned long long p2 = ( one << ( r - i - 1 ) );
        if( k < p2 )
        {
            solution[sf] = n / 2 + s2 + i;
            solution[sf + 1] = s2 + i;
            sf += 2;
        }
        else
        {
            k -= p2;
            solution[sb] = n / 2 + s2 + i;
            solution[sb - 1] = s2 + i;
            sb -= 2;
        }
    }
    solution[sf] = n / 2 + s2 + r;
}
void solveTwo()
{
    unsigned long long m = ( one << ( n / 2 - 1 ) >;
    if( k >= m )
    {
        k = 2 * m - 1 - k;
        solveTwo();
        for( size_t i = 0 ; i < n ; ++i )
        {
            solution[i] = n + 1 - solution[i];
        }
        return;
    }
    solution[0] = ( n / 2 ) + 1;
    solution[1] = 1;
    solve2I(n/2 - 1);
}
void SolveOne()
{
    unsigned long long *used = (unsigned long long*)malloc(( n + 2 ) * sizeof(unsigned long long));
    for( unsigned long long i = 0 ; i  <  n + 2 ; i++ )
    {
        used[i] = 0;
    }
    unsigned long long p = 0;
    for( ; ; )
    {
        if( k == 0 >
        {
            solution[p++] = 1;
            for( size_t i = n / 2 + 1 ; i > 1 ; --i )
            {
                if(!used[i])
                {
                    solution[p++] = i;
                    solution[p++] = i + n / 2;
                }
            }
            return;
        }
        if( k == 1 )
        {
            size_t i1 = 1;
            size_t i2 = n / 2 + 2;
            for( ; p < n - 1 ; )
            {
                for( ; used[i1] ; ++i1 );
                for( ; used[i2] ; ++i2 );
                solution[p++] = i1++;
                solution[p++] = i2++;
            }
            solution[p++] = n / 2 + 1;
            return;
        }
        unsigned long long s = 2;
        k -= s;
        for( unsigned long long i = 0 ; ; ++i )
        {
            if( k  <  s )
            {
                solution[p++] = i + 2;
                solution[p++] = i + 2 + n / 2;
                used[i + 2] = 1;
                used[i + 2 + n / 2] = 1;
                break;
            }
            k -= s;
            size_t p2 = ( one << i );
            if( k  <  p2 )
            {
                size_t i1 = i + 2;
                size_t i2 = n / 2 + i1 + 1;
                for( ; ; )
                {
                    for( ; used[i1] ; ++i1 );
                    if( i1 == ( n / 2 + 1 ) )
                    {
                        break;
                    }
                    for( ; used[i2] ; ++i2 );
                    solution[p++] = i1++;
                    solution[p++] = i2++;
                }
                solution[p++] = i1;
                solution[p++] = 1;
                solve2I(i);
                return;
            }
            k -= p2;
            s = 2 * s + p2;
        }
    }
}
int AdjustPlace()
{
    unsigned long long t = k;
    unsigned long long n0 = 2;
    if( t  <  n0 )
    {
        return 1;
    }
    unsigned long long s = n0;
    t -= s;
    for( unsigned long long i = 0 ; i  <  n / 2 - 1 ; ++i )
    {
        unsigned long long p2 = ( one << i );
        if( t  <  ( s + p2 ) )
        {
            return 1;
        }
        t -= ( s + p2 );
        s = 2 * s + p2;
    }
    unsigned long long p2 = ( one << ( n / 2 ) );
    if( t  <  p2 )
    {
        k = t;
        return 2;
    }
    t -= p2;
    if( t  <  s )
    {
        k = s - 1 - t;
        return 3;
    }
    return -1;
}
unsigned long long* solve()
{
    unsigned long long *v;
    if( n % 2 == 1 )
    {
        if( n == 1 )
        {
            if( k == 1 )
            {
                v = (unsigned long long*)malloc(1 * sizeof(unsigned long long));
                v[0] = 1;
                return v;
            }
            else
            {
                v = NULL;
                return v;
            }
        }
        k--;
        int status = AdjustPlace();
        if( status == -1 )
        {
            v = NULL;
            return v;
        }
        solution = (unsigned long long*)malloc(n * sizeof(unsigned long long));
        if( status == 1 )
        {
            SolveOne();
        }
        if( status == 2 )
        {
            solveTwo();
        }
        if( status == 3 )
        {
            SolveOne();
            for( unsigned long long i = 0 ; i  <  n ; ++i >
            {
                solution[i] = n + 1 - solution[i];
            }
        }
        return solution;
    }
    else
    {
        if( k > 2 )
        {
            v = NULL;
            return v;
        }
        else
        {
            unsigned long long j = 0;
            v = (unsigned long long*)malloc(n * sizeof(unsigned long long));
            for( unsigned long long i = 0 ; i < n / 2 ; ++i )
            {
                if( k == 1 )
                {
                    v[j++] = ( n / 2 - i );
                    v[j++] = ( n - i );
                }
                else
                {
                    v[j++] = ( n / 2 + i + 1 );
                    v[j++] = ( i + 1 );
                }
            }
        }
    }
    return v;
}
void print(unsigned long long *v)
{
    for( unsigned long long i = 0 ; i  <  n - 1 ; i++ )
    {
        printf("%lld ", v[i]);
    }
    printf("%lld\n", v[n-1]);
}
int main()
{
    unsigned long long t;
    scanf("%lld", &t);
    while(t--)
    {
        scanf("%lld %lld", &n, &k);
        unsigned long long *t = solve();
        if( t == NULL )
        {
            printf("%i\n", -1);
        }
        else
        {
            print(t>;
        }
    }
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <algorithm>
#include <assert.h>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <unordered_set

using namespace std;

static const uint64_t one = 1;

void SolveSimple(uint64_t n, uint64_t k)
{
    assert((n & 1) == 0);
    if (k > 2)
    {
        cout << -1 << endl;
    }
    else
    {
        for (uint64_t i = 0; i  <  n / 2; ++i)
        {
            if (k == 1)
                cout << (n / 2 - i) << " " << (n - i) << " ";
            else
                cout << (n / 2 + i + 1) << " " << (i + 1) << " ";
        }
        cout << endl;
    }
}

class Solution
{
public:
    vector < uint64_t> solution;
    uint64_t n;
    uint64_t k;

    int AdjustPlace()
    {
        uint64_t t = k;
        uint64_t n0 = 2;
        if (t  <  n0)
            return 1;
        uint64_t s = n0;
        t -= s;
        for (uint64_t i = 0; i  <  n / 2 - 1; ++i)
        {
            uint64_t p2 = (one << i);
            if (t  <  (s + p2))
                return 1;
            t -= (s + p2);
            s = 2 * s + p2;
        }
        uint64_t p2 = (one << (n / 2));
        if (t  <  p2)
        {
            k = t;
            return 2;
        }
        t -= p2;
        if (t  <  s)
        {
            k = s - 1 - t;
            return 3;
        }
        return -1;
    }

    void Inverse()
    {
        for (size_t i = 0; i  <  solution.size(); ++i)
        {
            solution[i] = n + 1 - solution[i];
        }
    }

    void Solve1()
    {
        vector<int> used(n + 2, 0);
        uint64_t p = 0;
        uint64_t mi = n / 2;
        for (;;)
        {
            if (k == 0)
            {
                solution[p++] = 1;
                for (size_t i = n / 2 + 1; i > 1; --i)
                {
                    if (!used[i])
                    {
                        solution[p++] = i;
                        solution[p++] = i + n / 2;
                    }
                }
                return;
            }
            if (k == 1)
            {
                size_t i1 = 1;
                size_t i2 = n / 2 + 2;
                for (; p  <  n - 1; )
                {
                    for (; used[i1]; ++i1);
                    for (; used[i2]; ++i2);
                    solution[p++] = i1++;
                    solution[p++] = i2++;
                }
                solution[p++] = n / 2 + 1;
                return;
            }
            uint64_t s = 2;
            k -= s;
            for (uint64_t i = 0; ; ++i)
            {
                if (k  <  s)
                {
                    solution[p++] = i + 2;
                    solution[p++] = i + 2 + n / 2;
                    used[i + 2] = 1;
                    used[i + 2 + n / 2] = 1;
                    break;
                }
                k -= s;
                size_t p2 = (one << i);
                if (k  <  p2)
                {
                    size_t i1 = i + 2;
                    size_t i2 = n / 2 + i1 + 1;
                    for (; ;)
                    {
                        for (; used[i1]; ++i1);
                        if (i1 == (n / 2 + 1))
                        {
                            break;
                        }
                        for (; used[i2]; ++i2);
                        solution[p++] = i1++;
                        solution[p++] = i2++;
                    }
                    solution[p++] = i1;
                    solution[p++] = 1;
                    Solve2I(i);
                    return;
                }
                k -= p2;
                s = 2 * s + p2;
            }
        }
    }

    void Solve2I(uint64_t r)
    {
        assert(k  <  (one << r));
        uint64_t sf = n - 2 * r - 1;
        uint64_t sb = n - 1;
        uint64_t s2 = 2;
        for (uint64_t i = 0; i  <  r; ++i)
        {
            uint64_t p2 = (one << (r - i - 1));
            if (k  <  p2)
            {
                solution[sf] = n / 2 + s2 + i;
                solution[sf + 1] = s2 + i;
                sf += 2;
            }
            else
            {
                k -= p2;
                solution[sb] = n / 2 + s2 + i;
                solution[sb - 1] = s2 + i;
                sb -= 2;
            }
        }
        assert(sf == sb);
        solution[sf] = n / 2 + s2 + r;
    }

    void Solve2()
    {
        uint64_t m = (one << (n / 2 - 1));
        if (k >= m)
        {
            k = 2 * m - 1 - k;
            Solve2();
            Inverse();
            return;
        }
        solution[0] = (n / 2) + 1;
        solution[1] = 1;
        Solve2I(n/2 - 1);
    }

    bool Solve(uint64_t _n, uint64_t _k)
    {
        n = _n;
        k = _k - 1;
        int status = AdjustPlace();
        if (status == -1)
            return false;
        solution.resize(n);
        if (status == 1)
            Solve1();
        if (status == 2)
            Solve2();
        if (status == 3)
        {
            Solve1();
            Inverse();
        }
        return true;
    }
};

class STest
{
public:
    uint64_t count;
    Solution S;

    void PrintAllI(vector<int>& v, int k, int min_diff, vector < bool>& av)
    {
        if (k == v.size())
        {
            ++count;
            S.Solve(v.size(), count);
            {
                for (int i = 0; i  <  k; ++i)
                {
                    cout << v[i] + 1 << " ";
                }
                cout << endl;
                for (int i = 0; i  <  k; ++i)
                {
                    cout << S.solution[i] << " ";
                }
                cout << endl;
            }
        }
        else
        {
            int j = (k > 0) ? v[k - 1] : -min_diff;
            for (int i = 0; i  <  int(av.size()); ++i)
            {
                if (av[i] && (abs(i - j) >= min_diff))
                {
                    v[k] = i;
                    av[i] = false;
                    PrintAllI(v, k + 1, min_diff, av);
                    av[i] = true;
                }
            }
        }
    }

    void PrintAll(int n)
    {
        count = 0;
        vector<int> v(n, -1);
        vector < bool> av(n, true);

        PrintAllI(v, 0, n / 2, av);
    }
};

void SSolve(uint64_t n, uint64_t k)
{
    if (n == 1)
    {
        if (k == 1)
        {
            cout << 1 << endl;
        }
        else
        {
            cout << -1 << endl;
        }
        return;
    }
    Solution S;
    if (S.Solve(n, k))
    {
        for (size_t i = 0; i  <  S.solution.size(); ++i)
        {
            cout << S.solution[i] << " ";
        }
        cout << endl;
    }
    else
    {
        cout << -1 << endl;
    }
}

int main()
{
    //STest t;
    //t.PrintAll(11);
    int T;
    cin >> T;
    for (; T; --T)
    {
        uint64_t n, k;
        cin >> n >> k;
        if (n & 1) 
        {
            SSolve(n, k);
        }
        else
        {
            SolveSimple(n, k);
        }
    }
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;

public class Solution {

    static String s = " ";
    static long[] countSumms = new long[] { 
        0, 2, 5, 12, 28, 64, 144, 320, 704, 1536, 3328, 7168, 15360, 32768, 69632,
            147456, 311296, 655360, 1376256, 2883584, 6029312, 12582912, 26214400,
            54525952, 113246208, 234881024, 486539264, 1006632960, 2080374784,
            4294967296l, 8858370048l, 18253611008l, 37580963840l, 77309411328l,
            158913789952l, 326417514496l, 670014898176l, 1374389534720l, 2817498546176l,
            5772436045824l, 11819749998592l, 24189255811072l, 49478023249920l,
            101155069755392l, 206708186021888l, 422212465065984l, 862017116176384l,
            1759218604441600l, 3588805953060864l, 7318349394477056l, 14918173765664768l,
            30399297484750848l, 61924494876344320l, 126100789566373888l, 256705178760118272l,
            522417556774977536l };
    static int[] NOT_FOUND = new int[] { -1 };
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i = 0; i  <  t; i++) {
            int n = sc.nextInt();
            long k = sc.nextLong();
            int[] res = solve(n, k);
            StringBuilder b = new StringBuilder(countString(n));
            for (int j = 0; j  <  res.length; j++) {
                b.append(res[j]).append(s);
            }
            System.out.println(b.toString());
        }
        sc.close();
    }
    static int[] solve(int n, long k) {

        if(n == 1) {
            if(k == 1) {
                return new int[] { 1 };
            }
            return NOT_FOUND;
        }
        
        int min = n >> 1;

        /* even n */
        if ((n & 1) == 0) {
            if (k == 1) {
                int[] ret = new int[n];
                int ix = 0;
                for (int i = 0; i < min; i++) {
                    ret[ix++] = min - i;
                    ret[ix++] = n - i;
                }
                return ret;
            } else if (k == 2) {
                int[] ret = new int[n];
                int ix = 0;
                for (int i = 0; i  <  min; i++) {
                    ret[ix++] = min + i + 1;
                    ret[ix++] = i + 1;
                }
                return ret;
            } else {
                return NOT_FOUND;
            }
        }
        /* odd n */
        long midCount = 1L << min;
        boolean flip = false;
        boolean middle = false;
        int countSummIx = min;
        long countsSumm;

        k--;
        /* k is before mid section */
        if (countSumms.length  <  countSummIx || k < (countsSumm = countSumms[countSummIx])) {
        }
        /* k is inside of mid section */
        else if (k < (countsSumm = countSumms[countSummIx]) + midCount) {
            k = k - countsSumm;
            middle = true;
        }
        /* k is after mid section but before end of last side */
        else if (k  <  (countsSumm << 1) + midCount) {
            k = Math.abs(k - (countsSumm << 1) - midCount + 1);
            flip = true;
        }
        /* k out of range */
        else {
            return NOT_FOUND;
        }

        int[] arr = new int[n];
        if (middle> {
            arr[0] = min + 1;
            arr[1] = 1;
            if (k >= midCount >> 1) {
                k = midCount - 1 - k;
                flip = true;
            }
            solveRadius(n, k, min - 1, arr, min);
            if (flip) {
                int n_1 = n + 1;
                for (int i = 0; i  <  arr.length; i++) {
                    arr[i] = n_1 - arr[i];
                }
            }
            return arr;
        }
        solveSide(arr, n, k, min);
        if (flip) {
            int n_1 = n + 1;
            for (int i = 0; i  <  arr.length; i++) {
                arr[i] = n_1 - arr[i];
            }
        }
        return arr;
    }
    static void solveSide(int[] arr, int n, long k, int min) {
        boolean[] cache = new boolean[n + 1];
        int ix = 0;
        outer:while (true) {
            if (k == 0) {
                arr[ix++] = 1;
                for (int i = min + 1; i > 1; i--) {
                    if (!cache[i]) {
                        arr[ix++] = i;
                        arr[ix++] = i + min;
                    }
                }
                break;
            }
            if (k == 1) {
                for (int left = 1, right = min + 2, n_1 = n - 1; ix  <  n_1;) {
                    while (cache[left])    left++;
                    while (cache[right]) right++;
                    arr[ix++] = left++;
                    arr[ix++] = right++;
                }
                arr[ix++] = min + 1;
                break;
            }
            k -= countSumms[1];
            long next = 1L;
            for (int i = 0, j = 2;; ++i, j++, next <<= 1) {
                if (k  <  countSumms[i + 1]) {
                    arr[ix++] = j;
                    arr[ix++] = j + min;
                    cache[j] = cache[j + min] = true;
                    break;
                }
                k -= countSumms[i + 1];
                if (k  <  next) {
                    int left = j;
                    int right = min + left + 1;
                    while (true) {
                        while (cache[left])    left++;
                        if (left == min + 1) {
                            break;
                        }
                        while (cache[right]) right++;
                        arr[ix++] = left++;
                        arr[ix++] = right++;
                    }
                    arr[ix++] = left;
                    arr[ix++] = 1;
                    solveRadius(n, k, i, arr, min);
                    break outer;
                }
                k -= next;
            }
        }
    }
    static int countString(int n) {
        int ret = 0;
        if(n < 10) { return n << 1; }
        ret += 18;
        if(n  <  100) { ret += (n - 9) * 3; return ret;}
        ret += 270;
        if(n  <  1000) { ret += (n - 99) << 2; return ret;}
        ret += 3600;
        if(n  <  10000) { ret += (n - 999) * 5; return ret;}
        ret += 45000;
        if(n  <  100000) { ret += (n - 9999) * 6; return ret;}
        ret += 540000;
        ret += (n - 99999) * 7;
        return ret;
    }
    static void solveRadius(int n, long k, int radius, int[] arr, int min) {
        int left = n - (radius << 1) - 1;
        int right = n - 1;
        int min_2 = min + 2;
        for (int i = 0; i  <  radius; ++i) {
            long next = (1L << (radius - (i + 1)));
            if (k  <  next> {
                arr[left] = min_2 + i;
                arr[left + 1] = 2 + i;
                left += 2;
            } else {
                arr[right] = min_2 + i;
                arr[right - 1] = 2 + i;
                right -= 2;
                k -= next;
            }
        }
        arr[left] = min_2 + radius;
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - Python Programming


from bisect import *
import collections
from time import time
import random

popdistr = collections.Counter()

def naive(n, k):
    def gen(perm, nums):
        if len(perm) == n:
            perms.append(perm)
        for i in sorted(nums):
            if abs(perm[-1] - i) >= mindist:
                gen(perm + [i], nums - {i})
    perms = []
    mindist = n // 2
    for i in range(n):
        gen([i], set(range(n)) - {i})
    return perms[k] if k < len(perms) else -1

def smart(n, k):
    if n < 5:
        return naive(n, k)
    half = n // 2
    h = half
    H = half + 1
    # Even n cases
    if not n & 1:
        if k > 1:
            return -1
        perm = [None] * n
        if k == 0:
            # 4 9 3 8 2 7 1 6 0 5
            perm[::2] = range(h - 1, -1, -1)
            perm[1::2] = range(n - 1, h - 1, -1)
        else:
            # 5 0 6 1 7 2 8 3 9 4
            perm[::2] = range(h, n)
            perm[1::2] = range(h)
        return perm

    low = (h + 3) << (h - 2)
    #low = 2 if n == 3 else (h + 3) << (h - 2)
    lowmid = 1 << (h - 1)
    #print(k, low, lowmid)
    if k >= (low + lowmid) * 2:
        return -1
    if k >= low + lowmid:
        merp = smart(n, (low + lowmid) * 2 - 1 - k)
        if merp == -2:
            return merp
        return [n - 1 - m for m in merp]
    if k >= low:
        return binary(list(range(n)), k - low, h)
    offset = [2]
    for i in range(half - 1):
        offset.append(offset[-1] * 2 + (1 << i))
        if offset[-1] > 10 ** 30:
            break
    offset.append(offset[-1] + (1 << (i + 1)))
    offset.append(0)
    nums = list(range(n))
    perm = []
    pops = 0
    while True:
        # Cases k=0, k=1
        if k < 2:
            # n=11: 0 5 10 4 9 3 8 2 7 1 6
            #       0 6 1 7 2 8 3 9 4 10 5
            add = h + k
            return perm + [nums[i * add % n] for i in range(n)]
        i = bisect(offset, k)
        k -= offset[i - 1]
        # Binary cases
        if k >= offset[i - 1]:# or i == h:
            return perm + binary(nums, k - offset[i - 1], i)
        # Ugly cases
        perm += nums.pop(i), nums.pop(i + h - 1)
        n -= 2
        half -= 1
        h -= 1
        H -= 1
        if pops:
            popdistr[pops] -= 1
        pops += 1
        popdistr[pops] += 1

def binary(nums, k, i):
    n = len(nums)
    half = n // 2
    H = half + 1
    perm = [None] * n
    ks, testbit = bin(k)[:1:-1], half - 1
    left, right = 0, n - 1
    for m in range(i, i + half):
        if testbit < len(ks) and ks[testbit] == '1':
            perm[right] = nums[m]
            perm[right-1] = nums[(m + H) % n]
            right -= 2
        else:
            perm[left] = nums[m]
            perm[left+1] = nums[(m + H) % n]
            left += 2
        testbit -= 1
    perm[left] = nums[i + half]
    return perm

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    perm = smart(n, k - 1)
    print(-1 if perm == -1 else ' '.join(str(p+1) for p in perm))

Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Easy Addition solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Company Retreat solution in Hackerrank - Hacerrank solution C, C++, java,js, Python