Tuesdays are the days of Codo Dojo at RC where you pair with another person and try to solve a problem in one hour. This Tuesday’s problem was the Euler Problem no. 24. Here’s the problem –

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:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

I paired with Vaibhav and we tried to solve it in Python. Here’s one of the approaches we took to solve the problem.

And here’s the code in C++

But it was giving a slightly incorrect result, if you know what I mean. We were getting 278391560 but the correct answer is 2783915460. Can you tell the difference? It’s really only matter of a digit….

Anyway, I set on then finding out the mystery of the vanishing digit. And I found out that our algorithm was not tackling one of the cases where the number of permutations with rest of the digits exactly match the number of slots left to fill. Confusing statement, hence let me present another of my sketches –

It turns out that when we land in a situation like the above that means –

1. We know the first digit (in the above example’s case first, but in our earlier example’s case we have been calculating the first, second, third and so on digits).
2. The number of slots left in the set are completely filled up by the all possible permutations of the rest of the digits.

So what will be the largest possible number in the permutation of rest of the digits?

One easy way of getting them is – if the digits are in ascending order, you just have to read them in the opposite order.

In the smaller example’s case I know that
1. The first digit would be 1.
2. The rest of the digits are {0, 2). Hence the largest number from the permutation of {0, 2) is 20.

Hence the number is 120! Phew!

Here’s the code that fixed the bug –