## Sequence of digits from natural numbers

Around a year ago I was taking a part, as a candidate, in a recruitment process in one of the world’s biggest and most innovative software companies. One question was to propose an algorithm to solve the following problem:

Given an infinite sequence made up of digits (in base of 10) from subsequent natural numbers find an element at a given position.

So the sequence goes like that: 123456789101112131415161718192021… At positions from 1 to 9 we have digits corresponding to numbers from 1 to 9. Next two elements are 1 and 0 because these are digits from number 10 which comes after number 9. And so on.

As I was not happy with an algorithm proposition I’ve presented to my interviewer I’ve decided to work it out. And here it is! And it’s in Java!

# Solution description

The naive solution would be to generate the sequence in a loop by concatenating text representations of subsequent natural numbers until the sequence is longer than given position. Then one needs to get the element at the given position.

The complexity of the naive solution is linear: O(n). I wanted something better.

My solution consists of two parts:

1. Determine (in a loop):
1. How many digits (D) there are in a natural number that produced a sequence element (digit) at the given position?
2. How many digits (elements of the sequence) were produced by natural numbers having less then D digits?
2. Reduce the problem to finding an element of a sequence of digits made up from natural numbers having digits only.
1. Transform the given position in the initial sequence into a new position into this simplified sequence by subtracting a total number of digits produces by all natural numbers having less than D digits.
2. Which number having D digits is covering the element at the new position? This gives us an index of the D-digit number. It’s easy as every D elements of the new sequence is corresponding to a single D-digit number.
3. What this D-digit number is? It’s easy as this is the first D-digit natural number (10 ^ (D – 1)) plus the calculated index.
4. Which digit of this D-digit number corresponds to the given position? Easy again as this is the remainder of dividing the new position by D. This last step gives the answer to the problem.

Couple of findings:

• The number of natural numbers having D digits: 9 * 10 ^ (D – 1)
• There are 9 natural numbers with 1 digit, 90 natural numbers with 2 digits, etc.
• The number of digits contained in all natural numbers having D digits: D * 9 * 10 ^ (D – 1)
• All 1-digit natural numbers produce 9 digits, all 2-digits natural numbers produce 180 digits, and so on.

# The algorithm in Java

```public class WhatDigit {

public static char solve(int position) {
long n = position;

// part 1
int digits = 1;
long offset = 0;
long digitsCount = 9;
while (Math.addExact(offset, digitsCount) < n) {
offset += digitsCount;
++digits;
digitsCount = 9 * digits * BigInteger.TEN.pow(digits - 1).longValueExact();
}

// part 2
n -= offset + 1;
long numberIndex = n / digits;
long number = BigInteger.TEN.pow(digits - 1).longValueExact() + numberIndex;
int digitIndex = (int)(n % digits);
if (digitIndex > 0) {
number = number % BigInteger.TEN.pow(digits - digitIndex).longValueExact();
}
long element = number / BigInteger.TEN.pow(digits - digitIndex - 1).longValueExact();

return (char)(element + '0');
}
}
```

## Remarks

I believe the complexity is in order of O(log(n)) because:

1. The first part consists of a loop. The number of iterations is equal to the number of digits in the given position. Thus the number of iterations is proportional to the logarithm of the value of the given position.
2. The second part could be considered as having a contant-time complexity. However this heavily depends on the complexity of the used implementation of a power function (BigInteger.pow(int) in my case). This is probably a weakness of my solution as the complexity of this implemetation of a power function is rather not O(1)… There is a solution however. As we need only powers of 10 we can iteratively calculate higher and higher powers in the loop in the 1st part using multiplication only and keep them in a dictionary. The highest power of 10 we need is 10 ^ (digits – 1).

In couple of places in calculations based on `long` values I used methods like `Math.addExact(long, long)` or `BigInteger.longValueExact()`. It’s because I wanted overflows on `long` to be detected and signaled with an exception.

Question at the end: can the part 1 be done in a constant time? 🙂

Nice mind exercise! 