Leetcode Permutation Sequence problem solution

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;
}

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;
    }
};

class Solution {
    public String getPermutation(int n, int k) {
        
        List<Integer> l = new ArrayList<>();
        
        for(int i=1; i<=n; i++)
            l.add(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;
    }
}

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)

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++) {
            choice.Add(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();     
    }
}