Detailed mathematical approach

Problem Summary

Write a positive integer in base 10 as \(a_1a_2\cdots a_k\). It is called increasing when \(a_1 \le a_2 \le \cdots \le a_k\), decreasing when \(a_1 \ge a_2 \ge \cdots \ge a_k\), and bouncy when neither condition holds. The task is to find the least \(n\) such that exactly \(99\%\) of the integers from 1 to \(n\) are bouncy.

The implementations solve this instance directly. They scan upward through the integers, classify each one from its decimal digits, maintain a running count of bouncy values, and stop at the first exact hit. That search reaches \(n = 1{,}587{,}000\).

Mathematical Approach

The key observation is that the full decimal string is more information than we need. For Problem 112, everything is determined by the signs of adjacent digit differences.

The sign pattern of adjacent digit differences

Let the digits of \(n\) be \(a_1,a_2,\dots,a_k\), and define

$\Delta_i = a_{i+1} - a_i \qquad (1 \le i < k).$

Then the classification becomes

$\text{increasing} \iff \Delta_i \ge 0 \text{ for all } i,$

$\text{decreasing} \iff \Delta_i \le 0 \text{ for all } i,$

$\text{bouncy} \iff \text{some } \Delta_i > 0 \text{ and some } \Delta_j < 0.$

So the only state that matters is whether we have seen a positive adjacent difference and whether we have seen a negative adjacent difference. This immediately explains why one-digit and two-digit numbers can never be bouncy: there are not enough adjacent pairs to witness both directions.

A one-pass invariant

As we inspect the digits, we maintain two booleans. After examining any subset of adjacent pairs, the first records whether a rise has already appeared and the second records whether a fall has already appeared. This invariant is sufficient because later digits can add new evidence, but they can never erase a rise or fall that was already found.

That is why an early exit is correct. The moment both booleans become true, the number is irreversibly bouncy. The Python implementation checks adjacent characters from left to right; the C++ and Java implementations peel digits from right to left. Those two views are equivalent because every adjacent pair is still tested exactly once.

Running count and the exact threshold equation

Let \(B(n)\) denote the number of bouncy integers in \(\{1,2,\dots,n\}\). The search is driven by the recurrence

$B(0)=0,\qquad B(n)=B(n-1)+I(n),$

where \(I(n)=1\) if \(n\) is bouncy and \(I(n)=0\) otherwise. For the required proportion \(99/100\), we seek the least \(n\) satisfying

$\frac{B(n)}{n}=\frac{99}{100},$

or, equivalently,

$100\,B(n)=99\,n.$

This integer form matters. It avoids any floating-point rounding issue, and it matches the implementations exactly. More generally, the C++ version is written for an arbitrary rational target \(p/q\) and tests \(qB(n)=pn\). Also note that \(B(n)/n\) is not guaranteed to increase at every step, because the denominator always grows while the numerator sometimes stays fixed, so checking each \(n\) directly is the safe stopping rule.

Worked example

Consider \(n=155349\). Its adjacent digit differences are

$5-1=4,\qquad 5-5=0,\qquad 3-5=-2,\qquad 4-3=1,\qquad 9-4=5.$

We see both a positive difference and a negative difference, so 155349 is bouncy. By contrast, \(134468\) has only nonnegative adjacent differences and is increasing, while \(66420\) has only nonpositive adjacent differences and is decreasing.

The same recurrence then updates the running total by one on bouncy inputs and by zero on non-bouncy inputs. The implementations line up with the standard benchmark values: the least number with 50% bouncy values is 538, the least number with 90% is 21780, and the least number with 99% is \(1{,}587{,}000\).

Why direct search is enough here

The desired threshold occurs well below ten million, so the scan never needs to inspect more than seven digits for any one candidate. The main mathematical simplification is therefore not a closed-form counting identity, but the recognition that each integer can be classified with constant auxiliary state and a tiny amount of digit work.

How the Code Works

The implementation walks through \(1,2,3,\dots\) in order, classifies each integer as bouncy or non-bouncy, updates a running total, and stops at the first exact 99% hit.

Classifying one candidate

The C++, Python, and Java implementations all test whether both directions of change occur among adjacent digits. The Python version uses the decimal string directly. The C++ and Java versions stay in integer arithmetic and compare digits as they are peeled off. In every language, the scan terminates immediately once both a rise and a fall have been detected.

Maintaining the count and validating the search

After the digit test, the implementation adds one to the running total exactly when the current value is bouncy. It then checks the cross-multiplied equality for the target proportion. The general implementation also validates itself against two known milestones, 50% at 538 and 90% at 21780, before solving the final 99% case. Those checkpoints verify both the classification logic and the cumulative counting logic.

Complexity Analysis

If \(N\) is the first solution, then classifying one number costs \(O(d(n))\), where \(d(n)=\lfloor \log_{10} n \rfloor + 1\) is the number of decimal digits of \(n\). Summed over the entire search, this gives

$O\!\left(\sum_{n=1}^{N} d(n)\right)=O(N\log N)$

in the usual asymptotic sense.

For this problem, \(N=1{,}587{,}000\), so \(d(n)\le 7\) throughout the run. In practice that makes the algorithm effectively linear in \(N\), and it uses only \(O(1)\) extra memory.

Footnotes and References

1. Problem page: Project Euler 112 - Bouncy numbers
2. Decimal positional notation: Wikipedia - Positional notation
3. Monotonicity: Wikipedia - Monotonic function
4. Asymptotic complexity notation: Wikipedia - Big O notation