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


  • 0
    I

    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 {
    public:
        string getPermutation(int n, int k) {
    		--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];
    			str.erase(str.begin()+idx);
    		}
    		return result;
        }
    private:
    	int factorial(int n){
    		int fac = 1;
    		for (int i = 1; i<=n; ++i){
    			fac *= i;
    		}
    		return fac;
    	}
    };

  • 0
    S

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


  • 0
    I

    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.