[math && computing] // JAVA: Find the Digit (Efficiently)

---

So I wrote a little program to answer the following question from The USSR Olympiad Problem Book:

"All the integers beginning with one are written successively (that is 123456789101112131415...). What digit occupies the 206,788th position?"

Essentially, the program makes the number 1234567... using a loop, appending the index variable i to the end of the number as it increased by one each time through the loop. 

That is:

• 1st time through loop: i = 1 --> put i on end of number --> number = 1 --> increase i by 1.
• 2nd time through loop: i = 2 --> put i on the end of number --> number = 12 --> increase i by 1.
• 3rd time through loop: i = 2 --> put i on the end of number --> number = 123 --> increase i by 1.
• etc.

Then, the program uses the .charAt(206787) method to find digit at the 206,788th place in the large number.

Not knowing how many consecutive integers I would need to glue together to get a number that had at least 206,788 digits, I used 206788 as the last number appended before finding the 206788th digit. This, however, took forever.

In fact, to get a number 206788 digits long, the last number you need to append is . Hence, the program inefficiently used processing time creating a number over 4 times longer than it needed to be.

The simple solution would be just to run the loop that creates the large number for a shorter index - perhaps 1/4 the time. But if you want to change the position you're looking at, the ratio of "last number appended" to "number of digits in large number" changes. Say you want to look at the 100 position. If you create a number that appends 1 through 1/4 of 100, 25, then 1234567...232425 is only 41 digits long.

Below is a table of ratios related to the problem:

last number added	number of digits	(# digits)/(last # added)
1	1	1
2	2	1
…	…	…
9	9	1
10	11	1.1
11	13	1.181818182
12	15	1.25
…	…	…
98	187	1.908163265
99	189	1.909090909
100	192	1.92
101	195	1.930693069
102	198	1.941176471
…	…	…
108	216	2
109	219	2.009174312
110	222	2.018181818
…	…	…
998	2886	2.891783567
999	2889	2.891891892
1000	2893	2.893
1001	2897	2.894105894
1002	2901	2.895209581
…	…	…
1106	3317	2.999095841
1107	3321	3
1108	3325	3.000902527
1109	3329	3.001803427
…	…	…

To use the table above: if you want to look at the 3329th position in the number 1234567... you need to create a number in which the last appended number was at least 3329/3.001803427 = 1109, or 1234567...110711081109. If you want to look at the 222nd position, you need to create a number ending in 222/(2/9) = 110, or 1234567...108109110.

So, how do you create a mathematical expression to insert in to the for-loop condition that creates an appended number that is minimally long enough to examine the position you're interested in? Hmmm...

Here is the program:

import java.util.Scanner;

public class FindTheDigit {

public static void main (String[] args) {

Scanner input1 = new Scanner(System.in);

Scanner input2 = new Scanner(System.in);

String addTo = "";

int position;

char find;

String repeat = "Mouse";

char firstChar;

System.out.println ("All the integers beginning with one are written "

+ "successively (that is 123456789101112131415...). What digit "

+ "occupies the 206,788th position?");

do {

System.out.print("Look up the digit at which position?: ");

position = input1.nextInt();

for (int i = 1; i <= position; i++) { 

addTo += i; 

} 

System.out.println("# of digits for number 12345..." + position + ": " + addTo.length()); 

find = addTo.charAt(position - 1); 

System.out.println("Number at position " + position + " is " + find); 

addTo = ""; 

System.out.print("Find another digit?: "); 

repeat = input2.nextLine(); 

firstChar = repeat.charAt(0); 

} while (firstChar == 'y' || firstChar == 'Y'); 

} 

}

---