C solution with comments


  • 0
    M

    The approach here was to start from the solution for "Next Permutation" and then work towards optimizing it for "k" iterations.

    "Next Permutation" done 'k' times would give a brute force solution running into several mS. But we can attempt to leapfrog this iteration sequence. Because every (factorial(j) - 1) iterations, last 'j' locations of the string lines up in a descending order. This was a valuable entry point to reach the below submitted more optimized code.

    char* getPermutation(int n, int k)
    {
        //               1  2  3  4   5    6    7     8      9
        int fact[] = {0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
        char *ch = malloc(sizeof(char) * (n + 1));
        int i, j, num; // account for the first permutation
        int v;
    
        /* Trust but verify */
        if (!ch)
            return NULL;
    
        /* Create the array */
        for (i = 0; i < n; ++i)
            ch[i] = '1' + i;
        ch[i] = 0; // NULL terminate
    
        /* Loop the required number of iterations are done */
        for (num = k - 1; num; num -= (fact[j] * v))
        {
            char ct;
    
            /* Find the largest number whose factorial is less than num */
            for(j = 9; fact[j] > num; --j);
    
            /* The below two step transformation is equal to (j! * v)
               iterations of calculating next permutation:
               1. All the elements from offset "(n - 1) - j" to "(n - 1) - j + v - 1"
                  will shift by one to the right.
               2. And the value at offset "(n - 1) - j" would be replaced with the
                  character from "(n - 1) - j + v"
            */
            v = num / fact[j];
            ct = ch[(n - 1) - j + v];
            for (i = (n - 1) - j + v; i > (n - 1) - j; --i)
                ch[i] = ch[i - 1];
            ch[i] = ct;
        }
    
        /* Return the permutation */
        return ch;
    }
    

Log in to reply
 

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