Thought Process

This problem is a continuation of Problem 112. It is quite a bit harder and has a completely different strategy.

My idea was basically the same as everyone else's which was to use dynamic programming or recursion to count all the increasing and decreasing integers, then we can remove duplicates and we have our answer.

Imagine we have an array such that array[x] = number of decreasing integers of a certain digit length d  which start with x

For example:

1. d = 2

2. dec = [1, 2, 3, 4, 5, 6, 7, 8, 9]

   1. For example dec[3] = 4 since there are 3, 2-digit numbers that decrease and start with the number 3. They are 33, 32, 31, 30

Now how would we do the next iteration? that is find the amount of decreasing 3-digit numbers

Well, imagine we start again with the number 3, now we know that the next number to be decreasing must be 3, 2, 1, or 0, and it's going to be 2 digits long, which we have exactly calculated!

Therefore, if d = 3, then dec[x] = sum(dec[0:x + 1])

We do exactly the same for an increasing count, but take note that the increasing array should have 9 elements instead of 10, since a number cannot start with a 0.

Now just find the number of decreasing and increasing integers, sum them up and don't forget to remove the doubles (1, 2, ..., 9, 11, 22, ..., 99, ...) and you have your answer. I leave the specifics to you on how exactly to code this, if you've understood the idea it should be very easy!