Bouncy Numbers

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, $134468$.
Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, $66420$.
We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, $155349$.
Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand ($525$) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches $50\%$ is $538$.
Surprisingly, bouncy numbers become more and more common and by the time we reach $21780$ the proportion of bouncy numbers is equal to $90\%$.
Find the least number for which the proportion of bouncy numbers is exactly $99\%$.

This problem can be solved using dynamic programming.

We can set up two 3-dimensional DP [dynamic programming] tables, DP_incr[i][j][k] and DP_decr[i][j][k] where:

– i represents the number of processed digits,
– j represents the last digit in the current number,
– k = 0 indicates whether the current number has the same prefix as our chosen number, but k = 1 indicates otherwise.

DP_incr[i][j][k] and DP_decr[i][j][k] store the count of increasing and decreasing numbers, respectively, of length ‘i’, ending with digit ‘j’, and satisfying property ‘k’.

For a given number, the subroutine ‘isBouncy()’ checks whether the number is bouncy. For the count of increasing and decreasing numbers, you can implement a function like ‘count_numbers()’ to create and fill your DP tables using the dynamic programming approach.

Iterating from 1 to 9 for the first digit (a number can’t start with 0), the tables are usually initialized as DP_incr[1][j][0] = 1 and DP_decr[1][j][0] = 1.

For increasing numbers, you recursively define:
DP_incr[i][j][0] = DP_incr[i – 1][j – 1][0] + DP_incr[i][j – 1][0] if j is the next digit in your number.
DP_incr[i][j][1] = DP_incr[i – 1][j – 1][0] + DP_incr[i – 1][j – 1][1] + DP_incr[i][j – 1][1] otherwise.

And for decreasing numbers, you recursively define:
DP_decr[i][j][0] = DP_decr[i – 1][j + 1][0] + DP_decr[i][j + 1][0] if j is the next digit in your number.
DP_decr[i][j][1] = DP_decr[i – 1][j + 1][1] + DP_decr[i – 1][j + 1][0] + DP_decr[i][j + 1][1] otherwise.

When you are trying to find the smallest number such that exactly 99% of all numbers are bouncy, you can use a binary search to check for bounciness, keeping track of the total count of numbers which are not bouncy, hence helping to find the smallest number satisfying the 99% condition swiftly.

Apply the above method in a code you are comfortable with – like Python or C++ – keeping in mind the goal is to use these procedures to find the smallest number for which exactly 99% of the numbers below it are bouncy. A direct implementation of this approach will usually take up less than a second, hence quite efficient.

This solution makes use of dynamic programming and binary search to efficiently iterate over the possible numbers and compute the result.

More Answers: