# Permutation Sequence

## Problem

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

## Code - Java

public class Solution {

private int[] lkp = new int[10];

private int[] calculate(int n, int k) {
if (n == 1) {
int[] result = new int[10];
result[1] = 1;
return result;
}
int bandwidth = lkp[n] / n;
Integer current = (int) Math.ceil((double) (k) / bandwidth);

int remainder = k - (current - 1) * bandwidth;
int[] result = calculate(n - 1, remainder);
int size = result.length;
for (int i = 0; i < size; i++) {
if (result[i] >= current) {
result[i]++;
}
}
result[n] = current;
return result;
}

public String getPermutation(int n, int k) {

lkp[1] = 1;

for (int p = 2; p <= n; p++) {
lkp[p] = lkp[p - 1] * p;
}

int[] result = calculate(n, k);
String s = "";
for (int i = n; i >= 1; i--) {
s += result[i];
}
return s;
}
}