0458MediumMathBinary Search

Digit At A Spot On The Numbering Roll

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 numbering machine prints a continuous paper roll. It prints 1, then 2, then 3, and so on without end, laying the characters of each number down one after another with nothing at all between numbers. The roll therefore begins 123456789101112..., so the tenth and eleventh characters are the 1 and the 0 of the number ten.

Characters are counted from 1 at the start of the roll. Given spot, return the single digit printed at that character position, as an integer from 0 to 9.

spot may run into the billions, so the roll cannot be printed out and indexed: your work must not scale with spot itself.

Examples

Example 1

Input: spot = 47
Output: 8

Counting along the roll, character 47 falls inside the number 28 and is the second of its two characters.

Example 2

Input: spot = 190
Output: 1

Characters 1 to 189 cover every number up to 99, so character 190 is the first character of 100.

Example 3

Input: spot = 1002
Output: 0

Character 1002 falls inside the number 370, on its last character.

Constraints

1 <= spot <= 2^31 - 1

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 digit_at_spot(spot: int) -> int:

Java

public int digitAtSpot(int spot)

The intended approach

Time O(log spot), one round per block of equal-width numbers.Space O(1).

The roll splits into blocks of numbers that print the same number of characters: nine numbers print one character, ninety print two, nine hundred print three. Subtract whole blocks off the spot until the remainder falls inside one, which takes about ten rounds even at the largest allowed spot. Dividing the remainder by the block's character width names the number, and the remainder of that division names which of its characters is wanted, which is then read off with integer division.

Pythonentry point: digit_at_spot

def digit_at_spot(spot):
    # Skip whole blocks of equal-width numbers: there are 9 numbers of width 1,
    # 90 of width 2 and so on, so a handful of subtractions lands on the block
    # holding the spot. Then step to the number inside that block and read off
    # the digit.
    # O(log spot) time, O(1) extra space.
    width = 1
    members = 9
    while spot > width * members:
        spot -= width * members
        width += 1
        members *= 10
    offset = spot - 1
    number = 10 ** (width - 1) + offset // width
    return (number // 10 ** (width - 1 - offset % width)) % 10

The obvious version

Print the roll for real, appending numbers until it is long enough, then index into it. O(spot) time and memory, so only usable for small spots.

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_digit_at_spot(spot):
    roll = []
    total = 0
    value = 1
    while total < spot:
        text = str(value)
        roll.append(text)
        total += len(text)
        value += 1
    return int("".join(roll)[spot - 1])

How this problem was checked

Reference solution executed against 21 test cases — 21 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