Project Euler/112

Problem Statement

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%.

Approach

The goal is to find the least $ N $ such that the proportion of bouncy numbers $ \le N $ is exactly 99%. Equivalently, the count of non-bouncy numbers $ NB(N) $ must satisfy:

$ NB(N) = \frac{N}{100} $

This implies $ N $ must be a multiple of 100.

A number is non-bouncy if it is either increasing or decreasing. Numbers with all identical digits (e.g., 555) are both increasing and decreasing, so by inclusion-exclusion:

$ NB(N) = I(N) + D(N) - F(N) $

where $ I(N) $, $ D(N) $, and $ F(N) $ are the counts of increasing, decreasing, and flat (all digits identical) numbers $ \le N $, respectively.

Digit DP for Increasing Numbers

The function $ I(N) $ counts positive integers $ x \le N $ whose digits are non-decreasing from left to right. This is computed using a recursive Digit DP with memoization.

State variables:

• index — current digit position being processed (0 to number of digits in $ N $)
• prevDigit — the previous digit placed (0–9)
• isLessThan — whether the prefix constructed so far is already strictly less than the corresponding prefix of $ N $
• isLeadingZero — whether we are still in the leading-zero phase (no non-zero digit has been placed yet)

Transitions: At each position, iterate over possible digits $ d $ from 0 up to the bound (9 if isLessThan is true, otherwise the digit of $ N $ at that position). If isLeadingZero is active and $ d = 0 $, the leading-zero state continues. Once a non-zero digit is placed, subsequent digits must satisfy $ d \ge \text{prevDigit} $ to maintain the increasing property.

The DP result includes 0, so 1 is subtracted to count only positive integers.

Digit DP for Decreasing Numbers

The function $ D(N) $ is analogous but enforces non-increasing digits ($ d \le \text{prevDigit} $). The memoization table uses an extra slot (index 10) to represent the initial/leading-zero state where no previous digit constraint applies.

Counting Flat Numbers

Flat numbers are those with all digits identical (e.g., 7, 22, 999). The count $ F(N) $ is computed directly:

• For each digit length less than the length of $ N $, there are 9 flat numbers (one for each digit 1–9).
• For numbers with the same length as $ N $, each candidate flat number (111…1 through 999…9) is compared lexicographically to $ N $; if it is $ \le N $, it is counted.

Non-Bouncy Count

$ NB(N) = I(N) + D(N) - F(N) $

Search Strategy

The search begins at $ N = 1{,}000{,}000 $ (where the proportion of bouncy numbers is approximately 98.7%) and increments by 100. At each step, $ NB(N) $ is computed via the Digit DP routines. The first $ N $ satisfying $ NB(N) = N / 100 $ is the answer.

A timeout and an upper bound (50,000,000) are included as safety guards.

Solution

Link to solution: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem112.java