Nth in Concatenated Decimal String
Problem Overview
The infinite string is the positive integers written one after another, 123456789101112 and so on.
Intuition
The infinite string is the positive integers written one after another, 123456789101112 and so on. Counting characters one by one is too slow when the index is near two billion. Numbers with the same width form a block. There are 9 one digit numbers, 90 two digit numbers, 900 three digit numbers, and each number contributes that many characters. Subtract a whole block from the index while the index is still past the end of the block. What remains names one number and one offset inside it. The number is the first value of the block plus the quotient, and the offset is the remainder. Dividing that number by the right power of ten reads the chosen digit directly.
Algorithm
- 1Start at the one digit block. Its first number is 1 and it holds 9 numbers.
- 2While the remaining index is larger than the width times the count of numbers, subtract that many characters and move to the next width.
- 3The number is the block start plus (remaining minus 1) divided by the width.
- 4The place inside that number is the remainder. Shift until that digit sits in the ones place.
- 5Return that digit as a character.
Example Walkthrough
Input: n = 11
- 1. The one digit block 1 through 9 uses 9 characters, so index 11 has 2 left inside the two digit block.
- 2. Those two characters are the start of the number 10.
- 3. The second of them is 0.
Output: 0
Common Pitfalls
- • The index is 1 based. Dividing n by the width, instead of n minus 1, lands on the next number.
- • Subtract a block only when the index is strictly past it. The last character of a block still belongs to that block.
- • The product of width and count passes a 32 bit int once numbers have 9 digits. Keep the running index in a 64 bit integer.
- • Building the decimal text of the chosen number only to read one character repeats work the division already did.
// Approach: The infinite string is 123456789101112... Numbers with d digits
// contribute 9 * 10^(d-1) * d characters. Subtract whole groups until the
// remaining index falls inside one group, then the number and the offset
// inside it are division and remainder. That digit is read by shifting,
// without building the decimal text.
// Complexity: O(log n) time, O(1) extra space.
class Solution {
public char nthCharacter(int n) {
long rem = n;
long digits = 1;
long count = 9;
long start = 1;
while (rem > digits * count) {
rem -= digits * count;
digits++;
count *= 10;
start *= 10;
}
long num = start + (rem - 1) / digits;
long place = 1;
for (long i = (rem - 1) % digits + 1; i < digits; i++)
place *= 10;
return (char) ('0' + (num / place) % 10);
}
}