1466. Endless Number Ribbon
A printing press stamps the counting numbers 1, 2, 3, ... one after another onto an endless paper ribbon, with no gaps. The press writes every number in base b (digits 0 to 9 and then a to f for values 10 to 15) and never pads a number with leading zeros. In base 3 the ribbon begins 12101112202122100...
Given n and b, return the numeric value of the n-th digit on the ribbon, counting from 1. For example, with b = 16 the digit f is returned as 15. Do not build the ribbon: skip whole blocks of equally long numbers and then locate the exact number and digit. Intended time is O(log n) with O(1) space.
Example 1
- Input:
- n = 11, b = 10
- Output:
- 0
- Explanation:
The base-10 ribbon is 12345678910111213..., so digit 10 is the 1 of the number 10 and digit 11 is its 0.
Example 2
- Input:
- n = 7, b = 2
- Output:
- 0
- Explanation:
The base-2 ribbon is 1 10 11 100 ..., i.e. 1101110..., and its 7th digit is 0.
Example 3
- Input:
- n = 12, b = 16
- Output:
- 12
- Explanation:
The base-16 ribbon is 123456789abcdef10..., and the 12th digit is c, which has value 12.
Constraints
1 ≤ n ≤ 1015
2 ≤ b ≤ 16
Block sizes can pass 253 in the middle of the computation, so use BigInt in JavaScript and 64-bit integers elsewhere.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(log n)
- Space
- O(1)