An iterative solution for reference

• Recursion will use more memory, while this problem can be solved by iteration. I solved this problem before, but I didn't realize that using k = k-1 would avoid dealing with case k%(n-1)!==0. Rewrote this code, should be pretty concise now.

Only thing is that I have to use a list to store the remaining numbers, neither linkedlist nor arraylist are very efficient, anyone has a better idea?

The logic is as follows: for n numbers the permutations can be divided to (n-1)! groups, for n-1 numbers can be divided to (n-2)! groups, and so on. Thus k/(n-1)! indicates the index of current number, and k%(n-1)! denotes remaining index for the remaining n-1 numbers.
We keep doing this until n reaches 0, then we get n numbers permutations that is kth.

``````public String getPermutation(int n, int k) {
for (int i = 1; i <= n; i++) num.add(i);
int[] fact = new int[n];  // factorial
fact[0] = 1;
for (int i = 1; i < n; i++) fact[i] = i*fact[i-1];
k = k-1;
StringBuilder sb = new StringBuilder();
for (int i = n; i > 0; i--){
int ind = k/fact[i-1];
k = k%fact[i-1];
sb.append(num.get(ind));
num.remove(ind);
}
return sb.toString();
}``````

• Thanks for your post and explanation.

I think linkedlist is as efficient as you can get in order to store the remaining numbers. Linkedlist may require counting index to get to the number, but it is more efficient than an array for removing elements. I haven't seen a better solution yet.

We can reduce the memory usage for factorial a little by using just one integer, since we are going down in factorial anyway.

I think you meant "permutations can be divided into n groups with (n - 1)! elements in each group". Thus, k / (n - 1)! is the index among current n groups, and k % (n - 1)! is the index for next iteration.

``````public String getPermutation(int n, int k) {
for (int i = 1; i <= n; i++) list.add(i);
int fact = 1;
for (int i = 2; i <= n; i++) fact *= i; // factorial

StringBuilder strBuilder = new StringBuilder();
for (k--; n > 0; n--) {
fact /= n;
strBuilder.append(list.remove(k / fact));
k %= fact;
}

return strBuilder.toString();
}``````

• ``````class Solution:
# @return a string
def getPermutation(self, n, k):
if n==1:
return "1"
factorial=[0]*(n+1)
factorial[0]=1
factorial[1]=1

for i in range(2,n+1):
factorial[i]=factorial[i-1]*i

candidate=[str(x) for x in range(1,n+1)]
result=[]

position=n
k=k-1
while position>=1:
# k is betwwen factorial[position] and factorial[position+1]
multiple=k//factorial[position-1]
remaining=k%factorial[position-1]
result.append(candidate.pop(multiple))
if remaining==0:
result.extend(candidate)
break
k=remaining
position-=1

return "".join(result)
``````

The same idea..
in python

• great answers! thanks a lot

• More edition to your description of this idea:

For n numbers, permutations can be divided into n groups with (n - 1)! elements in each group. Thus, k / (n - 1)! is the group index among the current n (to be) sorted groups, and k % (n - 1)! is the sequence number k for next iteration.

• I have a solution with similar idea but I didn't use additional space to store the remaining elements.

Here is the main idea:

First, I create the array, let's say [1,2,3,4].

Second, based on the k, I will pick a certain element to place in the 0th position. Let's say we pick element 3 and the remaining array is [1,2,4]. Instead of storing the remaining elements in a separate lists, what I did is move 3 to the 0th position and shift [1,2] towards right by 1 position. Then the list become [3,1,2,4] and we know the remaining list by reading the array from the 1st position

``````public class Solution {

// k is 1-based
public String getPermutation(int n, int k) {
int[] nums = getNums(n);
permute(nums, k-1);
return convertArrayToString(nums);
}

// k is 0-based
public void permute(int[] nums, int k) {
int divisor = fact(nums.length-1);
for ( int i = 0; i <= nums.length-2; i++ ) {
int swapTime = k/divisor;
for ( int j = 1; j <= swapTime; j++ ) { swap(nums, i, i+j); }
k %= divisor; divisor /= nums.length-i-1;
}
}

// Helper Method
public int fact(int n) { return n <= 1 ? 1 : n*fact(n-1); }
public void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
public String convertArrayToString(int[] arr){
StringBuffer s = new StringBuffer();
for ( int element : arr ) { s.append(element); }
return s.toString();
}
public int[] getNums(int n) {
int[] nums = new int[n];
for ( int i = 0; i < nums.length; i++ ) { nums[i] = i+1; }
return nums;
}
}
``````

• Good solution. But I believe it is meaningless to discuss the operation on a list with at most of len 9

• `LinkedList` may be efficient at removing things, but it's slow at locating things and `remove(k / fact)` needs to locate the element first, which is O(n). You can get instant removals when using `iterator.remove()`, but I can't figure out how to apply it to this problem. As it is, `LinkedList` solutions are bound to be slower than `ArrayList` because of its slower nature.

• What's the complexity for this problem? Is it O(N) , any idea?

• I think it's O(1) since n cannot be larger than 9.

• TLE for input:
8
8590

So leetcode added more test case?

• k = k-1 is not intuitive, here is verbose code if not doing it, which is more intuitive.
e.g. 1234 for k = 6, we should keep 1 and reverse 234, note that the last state of permutation is always the reverse of the sequence.

``````public String getPermutation(int n, int k) {
for (int i = 1; i <= n; i++) num.add(i);
int[] fact = new int[n];  // factorial
fact[0] = 1;
for (int i = 1; i < n; i++) fact[i] = i*fact[i-1];
StringBuilder sb = new StringBuilder();
for (int i = n; i > 0; i--) {
if(k%fact[i-1]==0) { // we already found it
int ind = k/fact[i-1]-1;
sb.append(num.get(ind));
num.remove(ind);
Collections.reverse(num); // the final state is the reverse of rest number
for(int d : num)
sb.append(d);
return sb.toString();
} else {
int ind = k/fact[i-1];
k = k%fact[i-1];
sb.append(num.get(ind));
num.remove(ind);
}
}
return sb.toString();
}``````

• @pinkfloyda
I am confused with the k=k-1, Could you please give me more explanation about why we need k=k-1?

• example:
`n = 4, k = 14`:

1. We have `{1, 2, 3, 4}`, find the `14th` permutation.

List out all the permutations:

`1 + (permutations of 2, 3, 4)`
`2 + (permutations of 1, 3, 4)`
`3 + (permutations of 1, 2, 4)`
`4 + (permutations of 1, 2, 3)`

To find the 14th, we can see it falling to range `3 + (permutations of 1, 2, 4)`, since `1 + (permutations of 2, 3, 4)` and `2 + (permutations of 1, 3, 4)` could take the first `2 * (3!) = 12` permutations. So we can know the first number of result is `3`.

1. Then the question turn to be a smaller problem.
`{1, 2, 4}`, find the `2nd` permutation.

List out all the permutations:
`1 + (permutations of 2, 4)`
`2 + (permutations of 1, 4)`
`4 + (permutations of 1, 2)`

There are `2! + 2! + 2!`, `6` permutation. The `2nd` must be in range `1 + (permutations of 2, 4)`. So we can know the second number of result is `1`.

1. So the question turn be a smaller problem.
`{2, 4}`, find the `2nd` permutation. The answer is `(4, 2)`.

So the final result is `(3, 1, 4, 2)`

``````public String getPermutation(int n, int k) {

StringBuilder res = new StringBuilder();

int[] f = new int[n];
f[0] = 1;              // 0's factorial is 1

for(int i = 1; i < n; i++){
f[i] = f[i - 1] * i;
}

k--;   // 14th count from 1, turn to be 13th count from 0.

for(int i = n; i > 0; i--){
int idx = k / f[i - 1];
k = k % f[i - 1];

res.append(nums.get(idx));
nums.remove(idx);
}
return res.toString();
}``````

• Great solution.

For improvement, I don't think you can achieve constant time for both get and delete operation in any ordered data structure. You can use a Binary Search Tree with Rank to achieve O(logn) get and delete. An example of such data structure is Order Statistic Tree: https://en.wikipedia.org/wiki/Order_statistic_tree

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.