Problem 112: Bouncy Numbers

Project Euler Problem 112 Solution

EulerSolve provides an optimized solution for Project Euler Problem 112, Bouncy Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

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

Detailed mathematical approach

Problem Summary

Read the digits of a positive integer from left to right. The number is increasing if no digit is smaller than the digit to its left, as $134468$, decreasing if no digit is larger than the digit to its left, as $66420$, and bouncy if it is neither, as $155349$. Let $B(n)$ be the number of bouncy numbers among $1,2,\dots,n$, so that the proportion of bouncy numbers up to $n$ is $B(n)/n$. The statement notes that no number below $100$ is bouncy, that $525$ of the numbers below $1000$ are, that the proportion first reaches $50\%$ at $n=538$, and that it equals $90\%$ at $n=21780$. We must find the least $n$ for which the proportion is exactly $99\%$. ^[1]

The whole solution in one sentence: we test $1,2,3,\dots$ in order, call a number bouncy when its digits go up at one place and down at another, keep the running count $B(n)$, and stop at the first $n$ with $100\,B(n)=99\,n$, an exact test in whole numbers that the count provably cannot step over. Counting the rare non-bouncy numbers with binomial coefficients then shows where the search must stop and gives a second method that needs only a dozen jumps.

Mathematical Approach

1. Rises, falls and flat steps

Write the digits of a number as $d_1d_2\dots d_k$. Each pair of neighbouring digits is a step: a rise if $d_i\lt d_{i+1}$, a fall if $d_i\gt d_{i+1}$, and flat if the two digits are equal. Then

increasing means no fall: $d_1\le d_2\le\dots\le d_k$;
decreasing means no rise: $d_1\ge d_2\ge\dots\ge d_k$;
bouncy means at least one rise and at least one fall.

The steps of $134468$ are rise, rise, flat, rise, rise; those of $66420$ are flat, fall, fall, fall; those of $155349$ are rise, flat, fall, rise, rise, so it is bouncy. Comparing only the first and last digits would fail: $132$ ends higher than it starts but falls in the middle. Flat steps are allowed in both families: "increasing" is meant in the weak sense, also called non-decreasing, as for monotonic functions. ^[2] A number with neither rises nor falls, such as $7$ or $4444$, is both increasing and decreasing; these repdigits are the only numbers in both families, nine of each length.

To classify a number we read its steps once and keep two marks, "a rise has been seen" and "a fall has been seen". Both start off, and each step can only switch on its own mark, so after every step each mark tells whether its kind of step has occurred so far. A statement that is true before a loop and stays true after every pass is a loop invariant, the standard tool for proving loops correct. ^[3] It shows that the marks are right at the end, and that we may stop early: once both marks are on, later digits cannot remove them, so the number is bouncy.

2. Why bouncy numbers start at 101

A rise and a fall are two different steps, so a bouncy number has at least three digits, and below $100$ there is none. $100$ is decreasing, and $101$, which falls to $0$ and rises again, is the smallest bouncy number; then come $102,\dots,109$ and $120$. Among $100,\dots,199$ the increasing numbers have the digits $1,a,b$ with $1\le a\le b\le9$, which gives $45$ numbers, the decreasing ones are $100$, $110$ and $111$, and $111$ is in both lists. So $45+3-1=47$ of them are not bouncy and $53$ are bouncy.

3. The running count and an exact test

The count starts at $B(0)=0$ and grows by one at every bouncy number: $B(n)=B(n-1)+1$ if $n$ is bouncy and $B(n)=B(n-1)$ otherwise. Multiplying $B(n)/n=99/100$ by $100n$ gives a test in whole numbers, with no rounding at all:

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

Two details matter: the count must include $n$ itself before the test, because the proportion is taken over $1,\dots,n$, and the search starts at $n=1$, because $n=0$ satisfies the equation trivially. For the first checkpoint, $B(537)=268$, the bouncy number $538$ raises the count to $269$, and $2\cdot269=538$; likewise $B(21780)=19602$, which is $\tfrac9{10}\cdot21780$.

The proportion does not grow steadily: it rises a little at a bouncy number and falls at any other number, because $n$ grows and $B(n)$ does not. At $533$ it is $264/533\approx49.53\%$; the six numbers $534,\dots,539$ are bouncy, so at $539$ it is $270/539\approx50.09\%$; $540$ and $541$ are decreasing, so it is exactly $50\%$ at $540$ and below $50\%$ again at $541$. In all, the proportion is exactly $50\%$ at $538$, $540$, $548$, $550$, $576$ and $582$ and never again, which is why the problem asks for the least such number. It also rules out a binary search: "at least $50\%$" holds at $539$ but fails again at $541$.

4. A walk that never jumps over zero

Combine the two sides of the test into one number,

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

From $n-1$ to $n$, $D$ goes up by $1$ if $n$ is bouncy and down by $99$ otherwise, like a walker who climbs one step at every bouncy number and drops $99$ steps at every other one. It starts at $D(0)=0$, with $D(1)=-99$ and $D(99)=-9801$, and we want the least $n\ge1$ with $D(n)=0$.

The key point: climbing one step at a time, the walker cannot get from below $0$ to above $0$ without standing on $0$. So the first $n$ whose proportion is $99\%$ or more has a proportion of exactly $99\%$; for this problem "first reaches" and "is exactly" mean the same. Three consequences follow.

$D(n)\lt0$ for every $n$ below the result: until then the proportion stays below $99\%$.
The last step before the result goes up from $-1$, so the result is a bouncy number, like $538$ and $21780$.
With $c(n)=n-B(n)$, the number of non-bouncy numbers up to $n$, we have $D(n)=n-100\,c(n)$. So the result is the least $n\ge1$ with $n=100\,c(n)$: exactly one number in a hundred up to it is not bouncy, just as $538=2\cdot269$ and $21780=10\cdot2178$ for the checkpoints.

For a proportion $p/q$ in lowest terms the walk $D(n)=q\,B(n)-p\,n$ goes up by $q-p$ and down by $p$. The proportions $1/2$, $9/10$ and $99/100$ of the statement all have $q-p=1$. Otherwise the walk can jump over $0$: for $60\%=3/5$ it goes from $D(1517)=-1$ to $D(1518)=1$, and the proportion jumps from $59.987\%$ to $60.013\%$. A proportion of $100\%$ is never reached, because $1$ is not bouncy.

5. Counting increasing numbers with stars and bars

The non-bouncy numbers are easy to count. In an increasing $k$-digit number the first digit is at least $1$ and no later digit is smaller, so $0$ never occurs. The number is fixed once we know how many $1$s, $2$s, …, $9$s it contains, because these digits must stand in increasing order: two $1$s and one $2$ give only $112$. So it is a multiset of $k$ digits taken from nine, and such multisets are counted by stars and bars. ^[4] Write the digits as $k$ stars and separate the nine kinds of digit by $8$ bars, so that $133$ becomes *||**||||||: one $1$, no $2$, two $3$s and nothing larger. Every row of $k$ stars and $8$ bars is exactly one increasing number, and choosing the places of the $8$ bars among $k+8$ places gives

$$I_k=\binom{k+8}{8}.$$

For $k=2$ this is $\binom{10}{8}=45$: the numbers $11,\dots,19$, $22,\dots,29$, and so on down to $99$, that is, $9+8+\dots+1=45$. For $k=3$ it is $\binom{11}{8}=165$.

6. Decreasing numbers and the overlap

A decreasing number may contain $0$, as $66420$ does. Any multiset of $k$ digits from $0,\dots,9$, written from the largest digit to the smallest, is a decreasing $k$-digit number, unless all its digits are $0$. With $9$ bars between ten kinds of digit,

$$R_k=\binom{k+9}{9}-1 .$$

For $k=2$ these are $10,11$, then $20,21,22$, up to $90,\dots,99$: $2+3+\dots+10=54$ numbers. The nine repdigits are counted in both families. Inclusion–exclusion for two sets, $|X\cup Y|=|X|+|Y|-|X\cap Y|$, corrects this by subtracting them once, ^[5] so the number of non-bouncy $k$-digit numbers is

$$N_k=\binom{k+8}{8}+\binom{k+9}{9}-10 .$$

For $k=1,\dots,7$ this gives $9$, $90$, $375$, $1200$, $3279$, $7998$ and $17865$; for three digits, $165+219-9=375$. So $900-375=525$ three-digit numbers are bouncy, the $525$ of the statement, and $7800$, $86721$, $892002$ and $8982135$ of the numbers with four to seven digits. OEIS gives the same count in another form. ^[6]

7. All lengths at once

To add up $N_1+\dots+N_k$ we use the hockey-stick identity, ^[7] which sums one diagonal of Pascal's triangle:

$$\sum_{i=r}^{m}\binom{i}{r}=\binom{m+1}{r+1}.$$

It follows from Pascal's rule in the form

$$\binom{i}{r}=\binom{i+1}{r+1}-\binom{i}{r+1}:$$

in the sum neighbouring terms cancel, and $\binom{m+1}{r+1}-\binom{r}{r+1}$ is left, where $\binom{r}{r+1}=0$ because $r+1$ objects cannot be chosen from $r$. With $r=8$ and $r=9$, leaving out the first terms $\binom88=\binom99=1$, the number of non-bouncy numbers below $10^k$ becomes

$$\begin{aligned}c(10^k-1)={}&\binom{k+9}{9}+\binom{k+10}{10}\\&-10k-2 .\end{aligned}$$

For $k=1,\dots,5$ it is $9$, $99$, $474$, $1674$ and $4953$; for $k=3$, $220+286-32=474$, and $999-474=525$ as before. The follow-up Problem 113 asks for this count below a googol, that is, for $k=100$; its statement gives $12951$ non-bouncy numbers below a million and $277032$ below $10^{10}$, the values of the formula for $k=6$ and $k=10$. ^[8]

8. Why bouncy numbers take over, and where 99% is reached

Below $10^k$ the proportion of bouncy numbers is $52.55\%$, $83.26\%$, $95.05\%$, $98.70\%$ and $99.69\%$ for $k=3,4,5,6,7$. The reason is visible in the formula: the non-bouncy count is a polynomial in $k$ of degree $10$, with leading term $k^{10}/10!$, while the count of all numbers grows like $10^k$. So the share of non-bouncy numbers tends to $0$: about $2.8\cdot10^{-5}$ below $10^{10}$ and $4.0\cdot10^{-13}$ below $10^{20}$. For a $k$-digit $n$, at most $c(10^k-1)$ of the numbers up to $n$ are not bouncy, and $n\ge10^{k-1}$, so

$$\frac{c(n)}{n}\le\frac{c(10^k-1)}{10^{k-1}}.$$

The formula also locates the result. With $D(n)=n-100\,c(n)$ from Section 4,

$$\begin{aligned}D(10^6-1)&=999999-1295100\\&=-295101,\end{aligned}$$

$$\begin{aligned}D(10^7-1)&=9999999-3081600\\&=6918399.\end{aligned}$$

The walk is positive at $10^7-1$ and started negative, so by Section 4 it stood on $0$ below $10^7$. A negative value at $10^6-1$ does not exclude an earlier visit, but the scan does: below $10^6$ the proportion stays under $98.86\%$, so the result has seven digits. Afterwards the walk never returns to $0$. The scan finds no second hit below $10^7$, and from $10^7$ on the bound above gives $c(n)\lt n/100$. Indeed, by Section 7

$$\begin{aligned}&c(10^k-1)\lt U_k\\&\quad=\binom{k+9}{9}+\binom{k+10}{10},\end{aligned}$$

and $U_8=68068$ is less than $10^7/100$. From $k$ to $k+1$ the two binomial coefficients grow by the factors $(k+10)/(k+1)$ and $(k+11)/(k+1)$, both at most $19/9$ for $k\ge8$, while $10^{k-1}$ grows tenfold; so $U_k\lt10^{k-1}/100$ for every $k\ge8$.

9. Counting up to any number, digit by digit

Stars and bars also count up to any $n$ if we read $n$ from the left, as when comparing two numbers. For $n=538$:

increasing: $9+45=54$ numbers have one or two digits. A three-digit one below $538$ starts with $d=1,2,3,4$ and continues with a non-decreasing pair of digits from $d,\dots,9$, which gives $45+36+28+21=130$ numbers; a start with $5$ would need a second digit at most $3$, which is impossible. Total $184$.
decreasing: $9+54=63$ short ones; a start $d=1,2,3,4$ with a non-increasing pair from $0,\dots,d$ gives $3+6+10+15=34$; the start $5$ followed by $0$, $1$ or $2$ and a last digit not larger than that gives $1+2+3=6$; the start $53$ followed by $0,1,2,3$ gives $4$. Total $107$.
repdigits: the $18$ short ones and $111$, $222$, $333$, $444$, so $22$.

So $c(538)=184+107-22=269$ and $538=2\cdot269$: the $50\%$ checkpoint seen from the other side. The same steps work for any $n$ with $k$ digits. After the shorter lengths, $I_j$ and $R_j$ for $j\lt k$, we read $n$ from the left. At a place followed by $r$ places, each digit $d$ below the digit of $n$, and at least $1$ at the first place, adds $\binom{r+9-d}{r}$ numbers if it keeps the prefix increasing and $\binom{r+d}{r}$ if it keeps it decreasing. We go on only while the prefix of $n$ itself stays increasing, or decreasing, count $n$ if it is, and subtract the repdigits up to $n$ once. A smaller number of the same length first differs from $n$ at exactly one place, so it is counted once in each family it belongs to. For $n$ below $10^7$ this takes at most $82$ binomial coefficients.

10. Jumping instead of walking

By Section 4 the result $n^\ast$ is the least $n\ge1$ with $n=100\,c(n)$, the least fixed point of $f(n)=100\,c(n)$. Start at $n_0=1$ and repeat $n_{i+1}=f(n_i)$:

no overshoot: $c$ never decreases, so $n_i\le n^\ast$ gives $n_{i+1}=100\,c(n_i)$${}\le100\,c(n^\ast)=n^\ast$;
progress: for $n_i\lt n^\ast$, $D(n_i)\lt0$, so $n_{i+1}=n_i-D(n_i)\gt n_i$.

So the $n_i$ climb strictly to exactly $n^\ast$, and the first value that repeats is the result. For $90\%$ the rule is $n\mapsto10\,c(n)$, and it visits

$$\begin{aligned}&1,\ 10,\ 100,\ 1000,\ 4750,\\ &9540,\ 15000,\ 21030,\ 21750,\ 21780,\end{aligned}$$

with $c(1000)=475$ because $1000$ is decreasing, and $c(21780)=2178$, a fixed point. That is $9$ jumps; $50\%$ takes $19$ jumps and $99\%$ takes $12$. Higher proportions $(q-1)/q$ are just as easy with $n\mapsto q\,c(n)$: exactly $99.9\%$ first occurs at $42596000$ after $7$ jumps, $99.99\%$ at $1650050000$ after $8$, and $99.9999\%$ at a twelve-digit number after $7$, far beyond a comfortable scan.

11. Other proportions and other bases

Of the whole percentages from $1\%$ to $98\%$ only $17$ are ever met exactly: $15$, $20$, $48$, $50$, $52$, $70$, $75$, $80$, $84$, $90$, $91$, $92$, $94$, $95$, $96$, $97$ and $98$ percent. A scan below $10^7$ settles all of them, because such a percentage needs at least $2\%$ non-bouncy numbers, and from $10^7$ on there are fewer than $1\%$ (Section 8). Some are met exactly but not when first reached: $70\%=7/10$ is first passed at $n=2154$, where the walk jumps from $-1$ to $2$, and met exactly only at $n=2270$; the same happens for $48\%$, $52\%$, $84\%$ and $91\%$. In base $b\ge2$, with $b-1$ non-zero digits, the same steps give

$$\binom{k+b-1}{b-1}+\binom{k+b}{b}-bk-2$$

non-bouncy numbers below $b^k$, which brute force confirms for the bases $2$ to $10$ and small $k$; in binary this is $k(k+1)/2$, the numbers written as ones followed by zeros.

How the Code Works

The C++ program ^[9] keeps the target proportion in an Options structure, $99/100$ by default, which parse_arguments changes on --numerator= and --denominator=, each followed by decimal digits that parse_int_after_prefix reads. Other arguments, or a numerator below $1$ or above the denominator, give exit code $1$, provided the numbers fit in an int: parse_int_after_prefix does not check for overflow. Unless --skip-checkpoints is given, run_checkpoints requires solve(50, 100) to return $538$ and solve(90, 100) to return $21780$, with exit code $2$ otherwise; then main prints the result of solve for the requested proportion.

solve(numerator, denominator) is the walk of Sections 3 and 4: an int counter bouncy, a loop over $n=1,2,\dots$ without an upper limit, and, after the counter has been updated for $n$, the test bouncy * denominator == n * numerator. For the default proportion both products stay below $10^9\lt2^{31}$, so an int of at least $32$ bits is safe. Other options can overflow: for $99.9\%$ the products pass $2^{31}$ long before the hit at $42596000$, and for $60\%$, which is never met exactly, or for $100\%$ the loop has no correct value to stop at. Signed overflow is undefined behaviour in C++; ^[10] in test runs, --numerator=60 --denominator=100 printed $537102052$, where the proportion is about $99.98\%$ but the overflowed products happen to agree, and --numerator=3 --denominator=5 printed a negative number.

is_bouncy(n) keeps the two marks of Section 1 in the flags increasing and decreasing. It takes the last digit, n % 10, as prev, divides n by $10$ and walks to the left: each new digit d is the left neighbour of prev, so d < prev is a rise and sets increasing, and d > prev is a fall and sets decreasing. For $120$ it starts with prev equal to $0$ and the rest $12$, meets $2\gt0$, a fall, then $1\lt2$, a rise, and returns true.

The Java program has the same digit test in isBouncy and runs the loop of solve directly in main, with $99/100$ fixed and without options, checkpoints or an upper limit; its int always has $32$ bits, ^[11] so the bound above applies. The Python program reads the digits from the left: is_bouncy compares neighbouring characters of str(n), setting inc on a rise and dec on a fall. This follows the order of the digits because strings compare by the Unicode code points of their characters, ^[12] and '0' to '9' have the consecutive code points $48$ to $57$. Its solve loops over range(1, 10000000), that is up to $9999999$, which Section 8 shows is enough, and prints the first $n$ with bouncy * 100 == n * 99. Python's integers have no size limit.

Complexity and Verification

The scan classifies fewer than $10^7$ numbers, each with at most six pairs of neighbouring digits. For a result $N$ this bounds the work by a multiple of $N\log N$, since a number up to $N$ has about $\log_{10}N$ digits, but the early exit does better: the C++ loop looks at $2.61$ pairs per number on average up to the result, and at about $2.62$ up to $10^{10}$, so in practice the time is proportional to $N$. The C++ and Java programs keep a handful of integer variables; the Python program also builds the short string str(n) for each number. On a desktop computer, measured from start to finish, the C++ program with its two checkpoint searches takes about $0.01$ seconds, the Java program $0.03$ seconds, mostly start-up, and the Python program $0.4$ seconds. The jump method of Section 10 needs $12$ jumps, that is $13$ evaluations of $c(n)$ including the final check, with at most $36$ binomial coefficients each.

The C++ program checks the two checkpoints of the statement before it solves the problem. All three programs, compiled and run for this article, print the same number, which an independent implementation of Section 10 confirms. The C++ options reproduce the first exact hits $3088$ for $75\%$, $4770$ for $80\%$, $63720$ for $95\%$, $377650$ for $98\%$ and $2270$ for $70\%$, and the default run is clean under the address and undefined-behaviour sanitizers. The three digit tests agree with a comparison of the digits with their sorted order for every $n\le10^6$ in Python and every $n\lt10^7$ in C++ and Java. Brute force confirms Sections 5 to 7 for every length up to seven digits, and both the count of Section 9 and a dynamic programme over the digits at every $n\le300000$ and every multiple of $101$ below $10^7$. A scan with 64-bit counters confirms the values for $99.9\%$ and $99.99\%$ and finds no exact $60\%$ hit below $10^8$, and a scan of all $n\lt10^7$ finds exactly one $n$ with a proportion of exactly $99\%$. Apart from the two checkpoints, none of these checks is part of the published solutions.

Footnotes and References

The references supply the background facts; the walk argument of Section 4, the counts of Sections 5 to 9 and the jump method of Section 10 are derived in this article.

Project Euler 112 — Bouncy Numbers. The statement defines increasing, decreasing and bouncy numbers with the examples 134468, 66420 and 155349, gives the 525 bouncy numbers below one thousand and the checkpoints 538 for 50% and 21780 for 90%, and asks for the least number for which the proportion of bouncy numbers is exactly 99%.
Wikipedia — Monotonic function. A function is monotonically increasing, or non-decreasing, if x ≤ y implies f(x) ≤ f(y); the term weakly increasing avoids confusion with the strict version, and decreasing is defined likewise.
Wikipedia — Loop invariant. A loop invariant is a property of a loop that is true before and after each iteration; if it holds before the loop and the loop body preserves it, it still holds when the loop ends.
Wikipedia — Stars and bars (combinatorics). Theorem two: there are C(n + k − 1, k − 1) k-tuples of non-negative integers with sum n, as a row of n stars and k − 1 bars shows; this is also the number of multisets of size n taken from a set of size k.
Wikipedia — Inclusion–exclusion principle. For two finite sets, |A ∪ B| = |A| + |B| − |A ∩ B|, because the elements of both sets are counted twice by the first two terms.
OEIS A152054 — Bouncy numbers. The sequence 101, 102, …, 109, 120, 121, …; the entry gives 9·10^(n−1) − (n + 18)·C(n + 8, 8)/9 + 10 as the number of n-digit bouncy numbers, which agrees with Section 6 because C(n + 9, 9) = C(n + 8, 8)·(n + 9)/9.
Wikipedia — Hockey-stick identity. For integers n ≥ r ≥ 0, the sum of C(i, r) over i = r, …, n is C(n + 1, r + 1), proved there in several ways, among them a telescoping sum.
Project Euler 113 — Non-bouncy Numbers. The follow-up problem notes that only 12951 numbers below one million and 277032 below 10^10 are not bouncy, and asks how many below a googol, 10^100, are not bouncy.
C++ — Euler112.cpp. The linked immutable revision, with parse_arguments, is_bouncy, solve, run_checkpoints and the checkpoints 538 and 21780, is the implementation record for this article.
C++ working draft — [expr.pre], Expressions: preamble. Paragraph 4: the behaviour of evaluating an arithmetic expression such as a multiplication is undefined if its mathematical result is not in the range of representable values of its type, as for a 32-bit int product above 2^31 − 1.
Java Language Specification, Java SE 25 — §4.2.1, Integral Types and Values. The values of int are 32-bit signed two's-complement integers from −2147483648 to 2147483647, and §4.2.2 adds that the integer operators do not indicate overflow in any way.
Python language reference — Value comparisons. Strings compare lexicographically using the numerical Unicode code points of their characters, the results of the built-in function ord().

Problem 112 source code

C++

#include <iostream>
#include <string>

namespace {

struct Options {
    int numerator = 99;
    int denominator = 100;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--numerator=", options.numerator) ||
            parse_int_after_prefix(arg, "--denominator=", options.denominator)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.numerator >= 1 && options.denominator >= options.numerator;
}

bool is_bouncy(int n) {
    bool increasing = false;
    bool decreasing = false;

    int prev = n % 10;
    n /= 10;

    while (n > 0) {
        const int d = n % 10;
        if (d < prev) {
            increasing = true;
        } else if (d > prev) {
            decreasing = true;
        }
        if (increasing && decreasing) {
            return true;
        }
        prev = d;
        n /= 10;
    }

    return false;
}

int solve(const int numerator, const int denominator) {
    int bouncy = 0;

    for (int n = 1;; ++n) {
        if (is_bouncy(n)) {
            ++bouncy;
        }
        if (bouncy * denominator == n * numerator) {
            return n;
        }
    }
}

bool run_checkpoints() {
    if (solve(50, 100) != 538) {
        std::cerr << "Checkpoint failed for 50 percent threshold" << '\n';
        return false;
    }
    if (solve(90, 100) != 21780) {
        std::cerr << "Checkpoint failed for 90 percent threshold" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.numerator, options.denominator) << '\n';
    return 0;
}

Python

# Problem 112: Bouncy numbers
# Find n where proportion of bouncy numbers is exactly 99%.

def is_bouncy(n):
    s = str(n)
    inc = dec = False
    for i in range(1, len(s)):
        if s[i] > s[i-1]: inc = True
        elif s[i] < s[i-1]: dec = True
        if inc and dec: return True
    return False

def solve():
    bouncy = 0
    for n in range(1, 10000000):
        if is_bouncy(n):
            bouncy += 1
        if bouncy * 100 == n * 99:
            print(n)
            return

solve()

Java

public class Euler112 {
    static boolean isBouncy(int n) {
        boolean inc=false, dec=false; int prev=n%10; n/=10;
        while(n>0){int d=n%10;if(d<prev)inc=true;else if(d>prev)dec=true;if(inc&&dec)return true;prev=d;n/=10;}
        return false;
    }
    public static void main(String[] args) {
        int bouncy=0;
        for(int n=1;;n++){if(isBouncy(n))bouncy++;if(bouncy*100==n*99){System.out.println(n);return;}}
    }
}