class Solution {
    public String getPermutation(int n, int k) {
        String chooseFrom = "123456789";

        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        factorial[1] = 1;
        for (int i = 2; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        k = k - 1; // Why?
        StringBuilder sb = new StringBuilder();
        for (int i = n; i >= 1; i--) {
            int x = k / factorial[i - 1];
            k = k % factorial[i - 1];
            sb.append(chooseFrom.charAt(x));
            chooseFrom = chooseFrom.substring(0, x) + chooseFrom.substring(x + 1, chooseFrom.length());
        }
        return sb.toString();
    }
}