Problem 112: Bouncy Numbers

Mathematical Development

Definition 1. Let $n$ be a positive integer with decimal representation $d_1 d_2 \cdots d_k$ (left to right). We say $n$ is increasing if $d_i \leq d_{i+1}$ for all $1 \leq i < k$, decreasing if $d_i \geq d_{i+1}$ for all $1 \leq i < k$, and bouncy if it is neither increasing nor decreasing.

Theorem 1 (Small numbers are non-bouncy). Every positive integer $n < 100$ is non-bouncy.

Proof. A single-digit number ($n < 10$) has a digit sequence of length 1, which vacuously satisfies both the non-decreasing and non-increasing conditions. A two-digit number $d_1 d_2$ with $d_1 \geq 1$ satisfies either $d_1 \leq d_2$ or $d_1 > d_2$, since any two integers are totally ordered. In the first case $n$ is increasing; in the second, $n$ is decreasing (in fact, strictly so). Hence no number below 100 is bouncy. $\blacksquare$

Theorem 2 (Bouncy density approaches 1). Let $B(n)$ denote the number of bouncy integers in $\{1, 2, \ldots, n\}$. Then $B(n)/n \to 1$ as $n \to \infty$.

Proof. The count of non-bouncy (increasing or decreasing) positive integers with at most $k$ digits is a polynomial in $k$ of degree at most 10 (see Problem 113, where the exact formula is $\binom{k+9}{9} + \binom{k+10}{10} - 10k - 2$). The total count of positive integers with at most $k$ digits is $10^k - 1$. Since polynomial growth is dominated by exponential growth, the fraction of non-bouncy numbers tends to 0, and consequently $B(n)/n \to 1$. $\blacksquare$

Lemma 1 (Divisibility constraint). If $B(n)/n = 99/100$, then $100 \mid n$.

Proof. The equation $B(n)/n = 99/100$ is equivalent to $100 \cdot B(n) = 99n$, i.e., $n = 100(n - B(n))$. Since $n - B(n)$ is a positive integer (it counts the non-bouncy numbers up to $n$), it follows that $100 \mid n$. $\blacksquare$

Theorem 3 (Existence and computability). There exists a least $n$ with $B(n)/n = 99/100$, and a sequential scan over all positive integers finds it in finite time.

Proof. By Theorem 2, $B(n)/n$ eventually exceeds any constant less than 1, including $99/100$. At $n = 100$, $B(100) = 0$ (Theorem 1), so $B(100)/100 = 0 < 99/100$. By Lemma 1, the target must be a multiple of 100. As $n$ increases, the non-bouncy count $n - B(n)$ grows subexponentially while $n/100$ grows linearly, so a crossing must occur. A sequential scan checks every integer, maintains an exact count, and cannot miss the first qualifying $n$. $\blacksquare$

Editorial

There is no need for a combinatorial shortcut here because the target is the first integer reaching a prescribed bouncy ratio. That makes a sequential scan the natural approach: move upward through the integers, classify each one from its decimal digits, and keep an exact running count of how many bouncy numbers have appeared so far.

The digit test is simple. A number is bouncy precisely when its digit sequence contains both an increase and a decrease somewhere along the way. Once that classification is available, the search stops as soon as the exact equality $100 \cdot B(n) = 99n$ is met, which guarantees that the returned value is the least such integer.

Pseudocode

Set the bouncy count to zero.

Examine the positive integers in increasing order.
For each integer n:
    Scan its digits from left to right and record whether the sequence ever rises and whether it ever falls.
    If both events occur, mark n as bouncy and increase the running count.
    If 100 times the bouncy count equals 99 times n, return n.

Complexity Analysis

• Time. $O(N \log N)$ where $N = 1{,}587{,}000$ is the answer. Each number requires $O(\log n)$ work for digit extraction and comparison. The total work is $\sum_{n=1}^{N} O(\log n) = O(N \log N)$.
• Space. $O(\log N)$ for storing the digit representation of the current number.

Answer

#include <bits/stdc++.h>
using namespace std;

bool is_bouncy(int n) {
    int prev = n % 10;
    n /= 10;
    bool inc = true, dec = true;
    while (n > 0) {
        int d = n % 10;
        if (d > prev) inc = false;
        if (d < prev) dec = false;
        prev = d;
        n /= 10;
    }
    return !inc && !dec;
}

int main() {
    int bouncy = 0;
    for (int n = 1;; n++) {
        if (is_bouncy(n)) bouncy++;
        if (100 * bouncy == 99 * n) {
            cout << n << endl;
            return 0;
        }
    }
}

def is_bouncy(n):
    digits = []
    while n > 0:
        digits.append(n % 10)
        n //= 10
    digits.reverse()
    inc = all(digits[i] <= digits[i + 1] for i in range(len(digits) - 1))
    dec = all(digits[i] >= digits[i + 1] for i in range(len(digits) - 1))
    return not inc and not dec


def solve():
    bouncy = 0
    n = 0
    while True:
        n += 1
        if is_bouncy(n):
            bouncy += 1
        if 100 * bouncy == 99 * n:
            print(n)
            return


solve()