Tuesday, February 5, 2013

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;
}

The source code with unit tests is available at http://ideone.com/yogYbu.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to
http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.
 

5 comments:

  1. Replies
    1. Here the position starts from 0, so the digit at the position 5 is 5. In this post, the position 5 is different from the 5th position.

      Delete
  2. The last line return -1; in digitAtIndex is never called

    ReplyDelete
  3. If anyone wants it, here's my slightly more compact (less nicely broken out) solution that utilizes that Math library in java:

    public int FindDigit(int k) {
    if (k < 0) return -1;
    if (k < 10) return k;
    //keeps track of the number of digits in the solution's underlying number
    int digitCount = 1;
    //starts on the first ten digits as the possible range
    //then jumps to larger ranges if k is not in the range for the
    //set of numbers with that number of digits
    int tierStart = 1;
    int tierEnd = 10;
    while (k > tierEnd) {
    tierStart += tierEnd;
    tierEnd += (Math.Pow(10, digit) * 9 * (digit + 1));
    digit++;
    }
    //accounts for digits before that range
    int truePosition = k - tierStart;
    //readds the numbers before the range to get the actual number
    //that are represented in the digits that k is in
    int fullNumber = (truePosition / digits) + (Math.Pow(10, digit -1);
    //represents k's position in the full number
    int pos = tierMid % digits;
    while (pos > 0) {
    fullNumber = / 10;
    pos--;
    }
    return fullNumber % 10;
    }

    ReplyDelete
  4. Here is a more compact python code

    def find_digit_in_order(n):
    if n<10:
    return n

    p10 = 9
    rank = 1
    remain = n
    passed=0
    while remain-rank*p10>0:
    if rank == 1:
    remain = remain - 10
    passed = 9
    else:
    remain = remain - rank*p10
    passed = passed + p10
    p10 = p10 * 10
    rank = rank + 1

    num = passed + math.ceil(remain/rank)

    for i in range(math.floor(rank-remain%rank-1)):
    num = math.floor(num/10)
    return num%10

    ReplyDelete