title: Efficient algorithm to find the n-th digit in the string 112123123412345
body: <p>What is an efficient algorithm for finding the <em>digit</em> in nth position in the following string</p>
  
  <pre><code>112123123412345123456 ... 123456789101112 ...
  </code></pre>
  
  <p>Storing the entire string in memory is not feasible for very large n, so I am looking for an algorithm that can find the nth digit in the above string which works if n is very large (i.e. an alternative to just generating the first n digits of the string).</p>