# 15ms concise JAVA solution, O(n) with comments

• ``````public class Solution {
/*
Idea: construct the target sequence from the most significant position

Method: 1: construct a table to store the total permutation number for each position
e.g. if n = 5 then table[] = {1, 2, 6, 24, 120} which are 1!, 2!, 3!, 4! and 5!
construct a boolean table to store which number are used among [1, n], here [1, 5] are {f,f,f,f,f}
2: Suppose the target label is k, where k <= 120 according to the quesiton.
To determine the first number:
a) if k == 120, return 54321
b) if k < 24, it means the permutation does not involve the arrangement of the highest postion,
The first number is the first unused number, in this case, 1, meanwhich set used[1] = true;
c) if k < 120 && k > 24 ==> k/24 = a; k%24 = b;
if b == 0, it means there are b total permutation of 24
e.g. if a == 1, return 15432
if a == 2, return 25431
the current positions' number is the 'ath' unused number.
Then, append all unused number in descending order will give the answer
if b != 0, it means there are b total permutaion of 24 and partial permutation of 24
find the '(a + 1)th' unused number
assign k = b to keep finding the rest
performance :   Time O(n)
15ms pretty good

*/
public String getPermutation(int n, int k) {
int[] table = new int[n + 1];
table[1] = 1;
for (int i = 2; i <= n; i++) {
table[i] = table[i - 1] * i;
}
StringBuilder sb = new StringBuilder();
boolean[] used = new boolean[n + 1];
int index = n;
while (k > 0 && k < table[index]) {
while (table[index] > k) {
index --;
if (table[index] > k) {
}
}
int div = k / table[index];
k %= table[index];
div += k == 0 ? 0 : 1;
}
for (int i = n; i >= 1; i --) {
if (!used[i]) {
sb.append(i);
}
}
return sb.toString();
}

public void addOne(boolean[] used, StringBuilder sb, int pos) {
for (int i = 1; i < used.length; i ++) {
if (!used[i] && --pos == 0) {
sb.append(i);
used[i] = true;
}
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.