Nth Digit
Medium · Math · Math · Binary Search
Problem
Write the positive integers one after another with no separators:
123456789101112131415…
Given n, return the n-th digit of this infinite string, counting from 1. The answer is a single digit from 0 to 9.
Examples
Input: n = 7 Output: 7
The first nine digits are just 1 to 9.
Input: n = 12 Output: 1
Positions 10 and 11 hold "10", so position 12 is the first digit of 11.
Input: n = 190 Output: 1
Positions 1 to 189 cover 1 to 99 (9 + 180 digits), so position 190 is the first digit of 100.
Constraints
- 1 <= n <= 2^31 - 1
Approaches
- Walk the numbers one at a time — time O(n / log n), space O(1)
Follow-up
What if the string were the concatenation of the numbers in another base, or of the squares 1 4 9 16 25 …? The block idea still works whenever you can count how many terms have each length: find the block, then the term, then the digit.
Related problems
Start free on Cariara · Coding problems · System design studio
