Is there a bug? it seens that OJ didn't consider the cases when k is greater then n!.

  • 0

    I use cantor expansion to solve this problem in O(n^2) time complex, and was accept. But when I test a case with K greater than n! in my PC, I got a wrong answer. see the commented line. Even I commented that line, OJ accepted my answer.

    class Solution {
        string getPermutation(int n, int k) {
    	        //k %= factorial(n);     // OJ accepted the answer without this line.
            string str;
    		for (int i = 0 ; i< n; ++i){
    			str += (i + '1');
    		string result;
    		for (int j = 0; j<n; ++j){
    			int fac =factorial(n-j-1);
    			int idx = k/fac;
    			k = k%fac;
    			result += str[idx];
    		return result;
    	int factorial(int n){
    		int fac = 1;
    		for (int i = 1; i<=n; ++i){
    			fac *= i;
    		return fac;

  • 0

    Could you please elaborate on the 'wrong answer' you got when k is greater than n?

  • 0

    sorry for the ambiguous n!, by (n!), i mean the factorial of n. when given a k greater then (n!), i expect the cycle back permutation as (k%(n!+1)+1)--plus one because k starts at one--like what next_permutation will perform that way. without the commented line of my above code, my solution can not handle cases that k is greater than (n!), and it was accepted. so i think OJ does not test those cases so far.

Log in to reply

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