Table of Contents
1 Problem
An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021…
It can be seen that the \(12^{th}\) digit of the fractional part is 1.
If dn represents the nth digit of the fractional part, find the value of the following expression.
\begin{eqnarray*} d_{1} × d_{10} × d_{100} × d_{1000} × d_{10000} × d_{100000} × d_{1000000} \end{eqnarray*}
2 Solution
二分法,我们无法直接得知第ith的digit,但是容易知道number n所在的位置.要找ith的digit,其必夹在1~i number之间的某个位置.如：
找1000th的digit
- 其必夹在1~1000 number之间,易知 (1 + 1000) / 2 = 500 的最后一位0在序列中的位置为1392th(number 11的最后一位1的位置为13),比1000th大,则必在1~499间
- 如此往复,我们可以找到最接近的number 370,其最后一位0为1002th,则1000th为digit 3
依此法可以找到任意ith的digit
3 Answer
210
Source:C++