# Leetcode Permutation Sequence problem solution

Apr 11, 2023

In the Leetcode Permutation Sequence problem solution, The set [1, 2, 3, …, n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: “213”

Example 2:

Input: n = 4, k = 9
Output: “2314”

Example 3:

Input: n = 3, k = 1
Output: “123”

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

## Solution in C Programming

``````char * getPermutation(int n, int k){
int anscnt=0;
char *ans=malloc(sizeof(char)*(n+1));
ans[n]='\0';// for C you need to care about the end of the string , or you will get RE
if(n==1){
ans[0]='1';
return ans;
}
int picked[n+1];
memset(picked,0,sizeof(int)*(n+1));
int factorial=1;
for(int i=2;i<=n;i++){
//calculate the factorial or all number first, so we only need O(N) time on each factorial
factorial*=i;
}
for(int i=n-1;i>=1;i--){
factorial/=(i+1);// for each i , the factorial of it
int max,loccnt=0;
//max : subproblem answer's first number
if(k%factorial==0){
max=k/factorial-1;
}
else{
max=k/factorial;
}
k-=(max*factorial);// the index for the next subproblem
for(int j=1;j<=n;j++){
//choose the first number of the subproblem
if(picked[j]==0){
if(loccnt==max){
ans[anscnt++]=j+'0';
picked[j]=1;
break;
}
loccnt++;
}
}
if(k<=1){
// the rest are the sorted array , so we end the problem
for(int j=1;j<=n;j++){
if(picked[j]==0){
ans[anscnt++]=j+'0';
}
}
break;
}
}
return ans;
}``````

## Solution in C++ Programming

``````class Solution {
public:
string getPermutation(int n, int k) {
string res = "";
int ref[10] = {0,1,2,6,24,120,720,5040,40320,362880}; // reference array

bool arr[10]; //bool array for marking used integers
int idx = n-1, c = 1;
memset(arr,false,sizeof(arr));

while(idx > 0){
while(k - ref[idx] > 0){
k -= ref[idx]; //removing as many permutations as permissible
if(arr[c + 1] == false) c++;
else{
c++;
while(arr[c] == true) c++;
}
}
res += to_string(c); //attach c to res as this is the leading element which should go to this position
arr[c] = true; //mark this element as used
c = 1;
while(arr[c] == true) c++;
idx --; //next set of permutations will be one less than this set
}
res += to_string(c);
return res;
}
};``````

## Solution in Java Programming

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

List<Integer> l = new ArrayList<>();

for(int i=1; i<=n; i++)

int fact = factorial(n);

StringBuilder sb = new StringBuilder();
k = k-1;

for(int i=0; i<n ;i++){

int f =  fact / (n-i);
int ind = k / f;
sb.append(l.get(ind));
k = k%f;
fact = f;
l.remove(ind);

}
return sb.toString();
}

private int factorial(int n){
int p=1;
for(int i=1;i<=n;i++)
p*=i;
return p;
}
}``````

## Solution in Python Programming

``````class Solution:
def fact(self,n):
if n==1 or n==0:return 1
return n*self.fact(n-1)

def rec(self,A,n,B):
if n==0:return ''
if n==1:return str(A[0])
m=self.fact(n-1)
k=B//m
b=B%m
if b==0:
i=k-1
else:
i=k
return str(A[i])+self.rec(A[:i]+A[i+1:],n-1,B-(m*i))

def getPermutation(self, n, k):
A=[i for i in range(1,n+1)]
return self.rec(A,n,k)``````

## Solution in C# Programming

``````public class Solution {
public string GetPermutation(int n, int k) {
List<int> choice = new(n);
int f=1;
//initial choices are all numbers up to n in order
//also compute factorial here
for (int i = 1; i <= n; i++) {
if (i < 3) f = i; else f *= i;
}
StringBuilder sb = new(n);
for (int i = n; i > 1; i--) {
int band = f/i; //number of combinations for each position of the next choice of digit
int p = k / band;
int r = k % band;
if (r > 0) p++;
sb.Append(choice[p-1]);
choice.RemoveAt(p-1);
k -= (p-1) * band;
f /= i;
}
return sb.Append(choice[0]).ToString();
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.