1098HardMathDynamic ProgrammingRecursion

Ones Printed Across the Page Numbers

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A signwriter numbers pages from 1 up to n, printing each number in ordinary decimal with no leading zeros. When n is 0 nothing is printed at all.

Return how many times the digit 1 is printed across all those page numbers.

Examples

Example 1

Input: n = 25
Output: 13

The units place carries a 1 on pages 1, 11 and 21. The tens place carries one on every page from 10 through 19. That is thirteen printed digits.

Example 2

Input: n = 9
Output: 1

Among the single-digit pages only page 1 carries the digit.

Example 3

Input: n = 99
Output: 20

Ten pages carry a 1 in the tens place and ten pages carry one in the units place, so twenty digits are printed.

Constraints

0 <= n <= 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_digit_one(n: int) -> int:

Java

public int countDigitOne(int n)

The intended approach

Time O(log n) over the digit places of n.Space O(1).

Handle one digit place at a time and ask how many page numbers hold a `1` there. Split `n` around that place into the part above it, the digit sitting in it and the part below it. For the units place, the tens place, and so on, the numbers holding a `1` in that place come in runs: one run of `place` numbers for every completed block of ten in the part above. So the part above always contributes that many. What the current digit adds is what the three cases turn on. If it is above one, the run for the current block is complete too, so one more full run of `place` numbers lands. If it is exactly one, the run has only reached as far as the part below, giving that many plus the number itself. If it is zero, the run has not begun and nothing is added. Multiplying the place by ten each round walks every digit place of `n`, so the whole count comes out in as many steps as `n` has digits.

Pythonentry point: count_digit_one

def count_digit_one(n):
    if n <= 0:
        return 0
    total = 0
    place = 1
    while place <= n:
        above = n // (place * 10)
        digit = (n // place) % 10
        below = n % place
        if digit > 1:
            total += (above + 1) * place
        elif digit == 1:
            total += above * place + below + 1
        else:
            total += above * place
        place *= 10
    return total

The obvious version

Write out every page number from one to `n` and count the `1` characters in each. Costs the page count times the digits per page, which is far too slow once `n` reaches the millions.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_digit_one(n):
    total = 0
    for value in range(1, n + 1):
        for ch in str(value):
            if ch == "1":
                total += 1
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in