Discussing Coding Interview Questions from Google, Amazon, Facebook, Microsoft, etc

No. 38 - Digits in a Sequence

Problem: Numbers are serialized increasingly into a sequence in the format of 0123456789101112131415..., which each digit occupies a position in the sequence. For instance, the digit in the position 5 is 5, in the position 13 is 1, in the position 19 is 4, and so on.

Please write a function/method to get the digit on any given position.

Analysis: Let's take a specific position as an example to analyze this problem. For example, what is the digit at the position 1001?

The first 10 digits are for 10 numbers with only one digit (0, 1, 2, ..., 9). Since the position 1001 is beyond of the range of the first 10 digits, we continue to look for the digit at the position at 991 (991 = 1001 - 10) in the following sequence.

The next 180 digits are for 90 numbers with two digits, from 10 to 99. Since 991 is greater than 180, the digit at position 991 is beyond the numbers with two digits. Let's continue to get the 811 (811 = 991-180) in the following sequence.

The next 2700 digits are for 900 numbers with three digits, from 100 to 999. Since 811 is less than 2700, the position 811 should be inside a number with three digits.

Every number has three digits, so the position 811 should be the second digit of the 270-th nubmer starting from 100 (811 = 270 * 3 + 1). Therefore, the digit at the position 811 is the second digit in the number 370, which is digit 7.

The overall solution can be implemented with the following code:

int digitAtIndex(int index)

{
    if(index < 0)
        return -1;

    int digits = 1;

    while(true)
    {
        int numbers = countOfIntegers(digits);
        if(index < numbers * digits)
            return digitAtIndex(index, digits);

        index -= digits * numbers;

        digits++;
    }
    return -1;
}

We can get the count of integers with n digits via the following function:

int countOfIntegers(int digits)

{
    if(digits == 1)
        return 10;

    int count = 1;

    for(int i = 1; i < digits; ++i)
        count *= 10;
    return 9 * count;
}

After we know the digit inside an integer with m digits, we could get the digit with the following function:

int digitAtIndex(int index, int digits)

{
    int number = beginNumber(digits) + index / digits;
    int indexFromRight = digits - index % digits;
    for(int i = 1; i < indexFromRight; ++i)
        number /= 10;
    return number % 10;
}

In the function above, we need to know the first number with m digits. The first number with two digits is 10, and the first number with three digits is 100. These numbers can be calculated with the function below:

int beginNumber(int digits)

{
    if(digits == 1)
        return 0;

    int begin = 1;

    for(int i = 1; i < digits; ++i)
        begin *= 10;
    return begin;
}