A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
This is more of a math problem thatn anything. The key part of this problem is to use factorials. Notice in the example given that the first 6 lexicographic numbers are permutations of 0,1,2. So, we can utilize how many premutatiosn are required to filled 1,000,000 positions.
There are 10! Lexiographic permutations using 0-9 digits, equivalent to 3,628,800, which exceeds 1,000,000. Hence, we start at 9! We see that it takes, we went through all the digits that start with 0 or 1 since 9! = 362880. So 2*9! is 725760. Now, we have 274240 numbers left to go through. But we know that the starting digit is 2.
Now, since we have used one digit, there are 9 digits left. But we must check how many numbers starting with a particular number we went through. This is a similar process as above: 8! = 40320, 6*8! = 241920, now we have 32,320 digits to go through. We can keep doing this process and we are left with the 1,000,000th lexicographic number. Code is still provided!
Answer: 2783915460
Runtime: N/A