Description
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... The sequence concatenates all positive integers.
Examples
Input:
n = 11Output:
0Explanation:
Sequence is 123456789101112..., 11th digit is 0 from 10.
Input:
n = 3Output:
3Explanation:
The sequence is 123456789101112... The first 9 digits are single-digit numbers 1-9. The 3rd digit is 3.
Input:
n = 15Output:
2Explanation:
The sequence is 123456789101112131415... Single digits 1-9 take positions 1-9, then 10 takes positions 10-11, 11 takes positions 12-13, 12 takes positions 14-15. The 15th digit is 2 from the number 12.
Constraints
- •
1 ≤ n ≤ 2³¹ - 1