CF 1520B - Ordinary Numbers

CF 1520B - Ordinary Numbers

Rating: 800
Tags: brute force, math, number theory
Solve time: 4m 49s
Verified: yes

Solution

Problem Understanding

We are given multiple queries, and each query consists of a single positive integer $n$. For each $n$, we need to count how many numbers in the range from 1 to $n$ have all digits identical in their decimal representation.

These “ordinary” numbers have a very rigid structure. Every valid number is formed by choosing a digit from 1 to 9 and repeating it one or more times. So valid examples include 7, 88, 444, and 999999999, while numbers like 10, 101, or 123 are excluded because at least two digits differ.

The constraint $n \le 10^9$ means each number has at most 10 digits. This is the key structural limitation: there are only a small number of possible ordinary numbers overall, and they are extremely sparse within the range of all integers.

A naive approach would be to check every number from 1 to $n$, verifying whether all digits are equal. This would require inspecting up to $10^9$ numbers per query in the worst case, which is far beyond acceptable limits given $t \le 10^4$. Even a linear scan per test case is impossible.

Edge cases arise when $n$ is small or exactly matches an ordinary number. For example, if $n = 5$, the answer is 5 because every single-digit number is ordinary. If $n = 10$, the answer is still 9 because 10 is not ordinary. A careless approach that only counts based on digit length might incorrectly include 10 or other mixed-digit numbers.

The main subtlety is recognizing that the answer is not dependent on distribution or arithmetic properties of $n$, but purely on counting a very small structured set of candidates.

Approaches

A brute-force solution would iterate from 1 to $n$, convert each number to a string, and check whether all characters are identical. This is straightforward and correct because it directly follows the definition. However, its cost is proportional to $n \log n$ per test case due to digit checks, which becomes infeasible immediately when $n$ reaches $10^9$ and $t$ is large.

The key observation is that ordinary numbers have a fixed combinatorial structure. For each digit from 1 to 9, we can construct numbers like 1, 11, 111, 1111, and so on. For a fixed length $k$, there are exactly 9 ordinary numbers: one for each digit 1 through 9. The problem then reduces to counting how many such numbers are less than or equal to $n$.

Instead of iterating over all integers, we generate only these structured candidates. There are at most 9 digits and at most 10 lengths, so the total number of candidates is bounded by 90. This turns each query into a constant-time scan over a tiny fixed set.

The brute force works because it checks every number explicitly, but fails because the universe is huge. The observation that ordinary numbers are completely determined by digit choice and length collapses the search space from linear in $n$ to constant size.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(n \log n)$ per test case	$O(1)$	Too slow
Optimal	$O(1)$ per test case	$O(1)$	Accepted

Algorithm Walkthrough

We exploit the fact that every ordinary number can be generated by choosing a digit and repeating it.

1. Precompute all ordinary numbers up to $10^9$ by iterating over digit choices from 1 to 9 and building repeated-digit numbers of increasing length.

Each construction is done by starting from 0 and appending the same digit repeatedly, which forms a geometric growth in value. 2. Store all generated values in a list. 3. Sort the list so we can answer queries using binary search or simple counting. 4. For each query $n$, count how many precomputed values are less than or equal to $n$.

The counting step is effectively a prefix query over a sorted static array, which can be done with binary search in logarithmic time, though even linear scan over 90 elements is sufficient.

Why it works

Every ordinary number corresponds uniquely to a pair (digit, length). There are no duplicates because different digit-length constructions always produce distinct integers. Since we generate all such pairs exhaustively within the digit limit imposed by $10^9$, the precomputed set exactly matches the universe of valid answers. The final count for any $n$ is therefore just the number of elements in this complete set that do not exceed $n$.

Python Solution

import sys
input = sys.stdin.readline

# Precompute all ordinary numbers up to 1e9
ordinaries = []

for digit in range(1, 10):
    val = 0
    for _ in range(10):  # max 10 digits because n <= 1e9
        val = val * 10 + digit
        ordinaries.append(val)

ordinaries.sort()

t = int(input())
for _ in range(t):
    n = int(input())
    
    # count how many are <= n
    cnt = 0
    for x in ordinaries:
        if x <= n:
            cnt += 1
    print(cnt)

The code constructs all candidate ordinary numbers by fixing a digit and repeatedly appending it. Each generated value is stored in a global list, which is then sorted for monotonic querying.

For each test case, we iterate through the precomputed list and count how many values do not exceed $n$. Since the list size is only 90, this is effectively constant time per query.

A common implementation mistake is attempting to generate numbers only up to the digit length of $n$ dynamically per query. That complicates logic unnecessarily and risks off-by-one errors when handling boundary values like powers of ten. Precomputation avoids all such issues.

Worked Examples

We trace two inputs to see how the precomputed set is used.

Example 1: $n = 5$

step	current x	x ≤ n	count
1	1	yes	1
2	11	no	1
3	111	no	1

The scan stops contributing once values exceed 5. The result is 5 single-digit numbers, matching the fact that only 1 through 5 are valid ordinary numbers.

Example 2: $n = 100$

step	current x	x ≤ n	count
1	1	yes	1
...	...	...	...
9	9	yes	9
10	11	yes	10
11	22	yes	11
18	99	yes	18
19	111	no	18

The count stabilizes at 18, corresponding to all one-digit and two-digit repeated-digit numbers.

This trace shows that once we pass 99, all remaining candidates exceed 100, so no further increments occur.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(t)$	Each test case checks at most 90 precomputed values
Space	$O(1)$	Only a fixed list of ordinary numbers is stored

The constraints allow up to $10^4$ queries, and each query performs constant work. The solution comfortably fits within both time and memory limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    ordinaries = []
    for digit in range(1, 10):
        val = 0
        for _ in range(10):
            val = val * 10 + digit
            ordinaries.append(val)
    ordinaries.sort()

    t = int(input())
    out = []
    for _ in range(t):
        n = int(input())
        cnt = 0
        for x in ordinaries:
            if x <= n:
                cnt += 1
        out.append(str(cnt))
    return "\n".join(out)

# provided samples
assert run("6\n1\n2\n3\n4\n5\n100\n") == "1\n2\n3\n4\n5\n18"

# minimum size
assert run("1\n1\n") == "1"

# boundary around 10
assert run("2\n9\n10\n") == "9\n9"

# exact ordinary number
assert run("1\n111\n") == "3"

# large value
assert run("1\n1000000000\n") == "90"

Test input	Expected output	What it validates
1	1	smallest possible input
9 / 10	9 / 9	boundary crossing over non-ordinary number
111	3	multi-digit repetition counting
1e9	90	full upper-bound coverage

Edge Cases

For $n = 10$, the algorithm counts only 1 through 9 because 10 is not a repeated-digit number. The precomputed list contains 11, so during counting, 11 is excluded correctly since it exceeds $n$.

For $n = 999999999$, all single-digit through nine-digit repeated numbers are included. The algorithm iterates through all 90 precomputed values and counts them all, producing 90.

For $n = 1$, only the first element in the list contributes. Since all other generated values are greater than 1, the result remains exactly 1.