1
class Solution {
2
  public String getPermutation(int n, int k) {
3
    int fact = 1;
4
    List<Integer> nums = new ArrayList<>();
5
    for (int i = 1; i < n; i++) {
6
      fact = fact * i;
7
      nums.add(i);
8
    }
9
    nums.add(n); // Add last permutation number.
10
    String res = "";
11
    k = k - 1; // We use 0 indexing.
12
    while (true) {
13
      res = res + nums.get(k / fact);
14
      nums.remove(k / fact);
15
      if (nums.size() == 0) break;
16

17
      k = k % fact;
18
      fact = fact / nums.size();
19
    }
20
    return res;
21
  }
22
}