HackerRank Find the permutation problem solution YASH PAL, 31 July 2024 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. Problem solution in 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 if 0: for k in range(7): print(naive(3, k)) input() 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) # offset[-1] = 0 #print(offset) 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] #print(offset, i, k, end=' ... ') # 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 if 1: 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)) Problem solution in 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; } } Problem solution in 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; } Problem solution in 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("%lldn", 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("%in", -1); } else { print(t); } } return 0; } coding problems data structure