class Solution {

  int[] factorials;

  public String getPermutation(int n, int k) {
    ArrayList<Integer> nums = new ArrayList();
    nums.add(1);

    factorials = new int[n];
    factorials[0] = 1;

    // calculate all factorials from 1 to n
    for (int i = 1; i < n; i ++) {
      factorials[i] = factorials[i - 1] * i;

      nums.add(i + 1);
    }

    StringBuilder sb = new StringBuilder();

    helper(nums, k, sb);

    return sb.toString();
  }

  private void helper(ArrayList<Integer> nums, int k, StringBuilder sb) {
    // base case
    if (nums.size() <= 0) {
      return;
    }

    // get number of permutation
    int count = factorials[nums.size() - 1];

    // skip count blocks for selecting the index
    int selected = (k - 1) / count;

    sb.append(nums.get(selected));

    nums.remove(selected);

    // skip some blocks
    k = k - (selected * count);

    helper(nums, k, sb);
  }
}