# UVa 10706

## Contents

## 10706 - Number Sequence[edit]

## Summary[edit]

This problem involves a little bit of number theory and can be solved using binary search.

## Explanation[edit]

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.

## Gotchas[edit]

- Take care of the marginal cases properly (e.g.,
`Int32.MaxValue</syntaxhighlight>).`

## Notes[edit]

- I believe that there exist more elegant ways to solve this problem.

## Input[edit]

18
8
3
80
546
23423
65753
2345
45645756
546454
6786797
131231
78934124
68904565
123487907
5655
778888
101011
2147483647

## Output[edit]

2
2
0
2
3
1
5
5
2
5
9
7
5
7
1
5
5
2

## Solution[edit]

```
```