Problem Analysis
Champernowne's constant is formed by concatenating the positive integers into an endless decimal string. The naive way to find the millionth digit - actually building that string - is wasteful: it would require gigabytes of memory and linear time in the position. The decisive observation is that the string is not random at all; it is a stack of regular bands, where each band collects all the integers with the same number of digits. The 1-digit numbers (1 through 9) contribute 9 * 1 = 9 characters; the 2-digit numbers (10 through 99) contribute 90 * 2 = 180 characters; and in general the band of d-digit numbers holds 9 * 10^(d-1) integers, each contributing d characters, for a band length of d * 9 * 10^(d-1) characters.
Because each band's length has a closed-form formula, I can locate any digit by accumulating band lengths - a running prefix sum - until the total first reaches or exceeds the target position. That tells me which band the position falls in; two integer operations (floor division and modulo) then pinpoint the exact integer and the exact digit within it. The number of bands to examine is bounded by the number of digits in the target position, so each lookup costs O(log n) integer operations. Since the problem asks for only a handful of digits (positions 10^0 through 10^6), the total work is a few dozen integer operations and the runtime is effectively immeasurable.
Solution Approach
Arithmetic band-walk (Python and C)
The Python file p0040_s0.py and the C file p0040_s0.c implement the same algorithm. The core lookup is get_nth_digit_champernowne_s_constant in Python and get_nth_digit_champernowne in C.
Step 1 - find the band. I keep two running totals: length_till_num_digits, the number of characters contributed by all bands strictly before the current one, and length_with_num_digits, the same total after including the current band. On each iteration I increment num_digits, copy the old running total into length_till_num_digits, then add the band length num_digits * 9 * 10^(num_digits-1). I stop as soon as length_with_num_digits reaches or exceeds n. At that point num_digits is the digit-length of the numbers in the band containing position n, and the two totals bracket that band's start and end. This is the prefix sum comparison made concrete.
Step 2 - find the offset within the band. I compute offset_of_number = n - length_till_num_digits - 1. Subtracting length_till_num_digits measures how far into the band we are; the extra -1 converts the problem's 1-based digit numbering into a 0-based index. Then floor division by num_digits gives the index of the number within the band, and the modulo gives the index of the digit within that number.
Step 3 - recover the digit. The first number in the d-digit band is 10^(d-1), so the target number is 10^(num_digits-1) + offset_of_number // num_digits. In Python I render the number with str and index the requested character, converting back to int. In C I format the number into a small stack buffer with snprintf and subtract '0' from the indexed character.
The driver loops over k from 0 to i inclusive, querying position 10^k each time and accumulating the product. Python expresses this declaratively with functools.reduce folding a multiplication over a generator. C uses a plain loop, multiplying the running pos by 10 on each iteration to avoid recomputing the power. Both compute 10^(num_digits-1) and the band length with short explicit multiplication loops in C, which sidesteps the floating-point inaccuracy that pow would introduce.