class Solution {
    public String getPermutation(int n, int k) {
        String res = "";
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 1;i<=n;i++) {
            list.add(i);
        }
        int fac = getFactorial(--n);
        k--;
        
        while(n>0) {
            res += list.remove(k/fac)+"";
            k = k%fac;
            fac /= (n--);
        }
        res += list.remove(0) + "";
        return res;
    }
    
    public int getFactorial(int a) {
        int num = 1;
        for(int i = 1;i<=a;i++) {
            num *= i;
        }
        return num;
    }
}