Champernowne's Constant
The problem
Concatenating the positive integers gives the decimal 0.123456789101112…. Find the product of its digits at positions 1, 10, 100, …, 1,000,000.
My solution
I generate the digits into a LinkedList<Integer> until it holds at least a million, copy it to an array, and multiply the entries at indices 0, 9, 99, …, 999,999.
To emit each number’s digits in order without using strings, I reverse the number arithmetically and pop digits off the reversed copy. Reversal drops trailing zeros (10 reversed is 1), so the code also divides a second copy of the original once per popped digit; whatever is left in it afterward counts the lost zeros, which get appended:
while(rev != 0) {
list.add(rev % 10);
size++;
rev /= 10;
num /= 10;
}
while(num != 0) {
num /= 10;
list.add(0);
size++;
}
Notes
The digit at position k can also be found without generating anything: skip the 9 digits of one-digit numbers, the 180 of two-digit numbers and so on until k falls inside a block, then index into the right number.