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!

Advertisements

About krzysztoftomaszewski

I've got M.Sc. in software engineering. I graduated in 2005 at Institute of Computer Science, Warsaw University of Technology, Faculty of Electronics and Information Technology. I'm working on computer software design and engineering continuously since 2004.
This entry was posted in Java and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s