10706 - Number Sequence
This problem involves a little bit of number theory and can be solved using binary search.
Let the sequence be , where consists of positive integer numbers ranging from 1 to k. A natural question is, what is the length or the number of digits of . It is not hard to write a small subroutine to compute the length of . Let denote the length of some sequence S and the number of digits of k. Then by noticing that we have . Since is bounded in this problem, it can be estimated that . This rough estimation helps us to pinpoint the biggest possible k value involved in this problem. Actually . 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 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 , 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