Project Euler 862 - Larger Digit Permutation

Official link: https://projecteuler.net/problem=862

Thought Process

I solved Problem 885 first which is quite similar, please view that page to understand the next statement. There are 21C9 = 293,930 increasing numbers in this case so it is easy to brute force.

Instead of counting all the permutations of the digits, we need to count the number of permutations without any leading 0's. 

The way I did this is, let x be the increasing number we have:

Hence the total number of permutations without leading 0's is k = (n - d0)!(n - 1)!/(n - 1 - d0)!/(d1!d2!d3!d4!d5!d6!d7!d8!d9!), then we can directly sum T(x) for these k permutations using k(k - 1)/2.

Example:

Take x = 0223, then d0 = 1, d2 = 2, d3 = 1, hence we have k = 3!3!/2!/2! = 9, as shown above. Then T(2023) = 8, T(2032) = 7, ... , T(3022) = 2, T(3202) = 1, T(3220) = 0, so sum of all these T(x) = 9*8/2 = 36.

Interactive Code

Input an integer (yourinput)

Code will output S(yourinput)