# Project Euler 113 – Non-bouncy numbers

#### Posted on January 24, 2016

##### Last updated on June 18, 2017

This stood out immediately to me as Dynamic Programming, although I’m certain with a bit of ingenuity you could come up with a closed form equation. I’m lazy though, and will just get the computer to do it for me!

Assume we have a number $$d_1 d_2 d_3 \ldots d_n$$ where $$\forall_{i} 0 \leq d_i \leq 9$$ except the for the first digit we have $$d_1 \neq 0$$ as a number can’t start with a zero.

Then, consider how to count the number of increasing numbers of length $$i$$ beginning with the digit $$k$$

\begin{align} f_{inc}(1,k) &= 1 \\ f_{inc}(i,k) &= \sum_{j=k}^9 f_{inc}(i-1,j) \end{align}

Similarly for decreasing numbers except we have to take care of the zero.

\begin{align} f_{dec}(1,k) &= 1 \\ f_{dec}(1,0) &= 1 \\ f_{dec}(i,k) &= \sum_{j=0}^k f_{dec}(i-1,j) \end{align}

Now, given $$N$$ we can compute how many non-bouncy numbers of length at most $$N$$ there are. We count all the increasing numbers beginning with all possible digits and we count all the decreasing digits beginning with all the possible digits. There is a problem: We have double counted numbers like $$111$$, or $$3333$$, basically all numbers composed of the same digits. For every length $$N$$, there are only exactly $$9$$ such numbers so we can just easily subtract that.

Then the answer for the how many non-bouncy numbers of length at most $$N$$ there are is:

$total(N) = \sum_{i=0}^{100} \sum_{k=1}^{9} \left( f_{inc}\left(i,k\right) + f_{dec}\left(i,k\right) \right) - 9N$

Now we can convert this to Java code. You could convert it to only use one array but for sake of simplicity I used two arrays.

Run the following, and you get the answer $$51161058134250$$ instantly.

Markdown SHA1: 3a77e44dd26051f6c36968ea76ebccf316f90fca