Digit on the Counting Ribbon

MediumMath & Geometry

Problem

A ticker-tape machine prints the positive integers one after another with no separators: 123456789101112131415....

Return the digit at position k of the ribbon (positions start at 1).

Example 1

Input:
k = 3
Output:
3

Example 2

Input:
k = 11
Output:
0

Positions 10 and 11 hold the two digits of 10, so position 11 is 0.

Example 3

Input:
k = 190
Output:
1

Numbers 1..99 use 9 + 180 = 189 digits, so position 190 is the first digit of 100.

Constraints

  • 1 ≤ k ≤ 10^15

Hint

Show the first hint

Building the ribbon up to position 10^15 is impossible. Group the numbers by how many digits they have.

Walkthrough

How to approach it

01Clarify before coding

  • Is k 1-indexed? Yes: k = 1 is the digit 1.
  • How large is k? Up to 10^15, so the answer must be computed arithmetically.
  • Do intermediate values fit in 53 bits? The largest block examined uses about 1.3 · 10^15 positions, so yes.

02Brute force

Append numbers to a string until it has k characters, then read position k.

Cost: O(k) time and memory: 10^15 characters.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.