10706 - Number Sequence
This problem involves a little bit of number theory and can be solved using binary search.
Let the sequence Ak be S1S2...Sk, where Sk consists of positive integer numbers ranging from 1 to k. A natural question is, what is the length or the number of digits of Ak. It is not hard to write a small subroutine to compute the length of Ak. Let len(S) denote the length of some sequence S and dk the number of digits of k. Then by noticing that len(Sk) = len(Sk - 1) + dk we have . Since dk is bounded in this problem, it can be estimated that len(Ak) = O(k2). This rough estimation helps us to pinpoint the biggest possible k value involved in this problem. Actually len(A31267) < 2,147,483,647 < len(A31268). With the knowledge of the maximum k value, given the index i of a certain digit, we can use the binary search to locate the Sk to which the digit belong. This technique is similar to the one used in quick sort and thus the details are ignored. After locating the Sk, the rest of the job is trivial.
- Take care of the marginal cases properly (e.g.,
- I believe that there exist more elegant ways to solve this problem.
18 8 3 80 546 23423 65753 2345 45645756 546454 6786797 131231 78934124 68904565 123487907 5655 778888 101011 2147483647
2 2 0 2 3 1 5 5 2 5 9 7 5 7 1 5 5 2