loading...

Daily Coding Challenge #40

wingkwong profile image wkw ・1 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
LeetCode - Permutation Sequence

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.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

Input: n = 3, k = 3
Output: "213"
Example 2:

Input: n = 4, k = 9
Output: "2314"
*/

class Solution {
public:
    string getPermutation(int n, int k) {
        string str;
        int cnt=1;
        // build the str from [1,2,3,...,n] 
        // e.g. 123..n
        while(n--)  str.push_back(cnt+++'0');
        // use next_permutation to find out the permutation 
        while(--k)  next_permutation(str.begin(),str.end());
        return str;
    }
};

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

πŸ† A Collection of my LeetCode Solutions with Explanations πŸ†

GitHub logo wingkwong / hackerrank

πŸ† A Collection of my HackerRank Solutions with Explanations πŸ†

GitHub logo wingkwong / codeforces

πŸ† A Collection of my Codeforces Solutions with Explanations πŸ†

GitHub logo wingkwong / atcoder

πŸ† A Collection of my AtCoder Solutions with Explanations πŸ†

Discussion

pic
Editor guide
Collapse
goshrow profile image
GOSHROW

If k might range up to n!, Wouldn't this code fail to accomodate to such large values. There is another elegant solution available to it which can scale better. geeksforgeeks.org/find-n-th-lexico...