public String getPermutation(int n, int k) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (k > factorial(n) || k <= 0 || n <= 0) {
			return new String();
		}
		StringBuilder sb = new StringBuilder();
		ArrayList<Integer> num = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			num.add(i);
		}
		System.out.println("size" + num.size());

		int[] factor = new int[n];// store factorial result to speed up
		for (int i = 0; i <= n - 1; i++) {
			factor[i] = factorial(i);
		}

		// determine the permutation digit by digit
		for (int i = 0; i < n; i++) {
			int f = factor[n - i - 1];
			int j = 0;
			while (j * f < k) {
				j++;
			}
			j--;
			k -= j * f;
			sb.append(String.valueOf(num.get(j)));
			num.remove(j);

		}
		return sb.toString();

	}