2
$\begingroup$

This was interview question.

When the input is a infinite sequence of numbers starting from 1, what is the nth digit?

e.g.) 123456789101112131415161718192021.....

here 28th digit is 1.

$\endgroup$
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? What are you looking for in an answer? Are you looking for an algorithm? Note that coding questions are off-topic here. If you're looking for an algorithm, what approaches did you consider? $\endgroup$ – D.W. Feb 29 '16 at 7:05
  • $\begingroup$ You'll find a lot of references on OEIS. $\endgroup$ – Gilles 'SO- stop being evil' Mar 11 '16 at 21:29
3
$\begingroup$

Just to add a concrete implementation to what was already said:

(defun nth-digit (n)
  (loop :with previous := 0
     :for i :upfrom 0
     :sum (* 9 (expt 10 i) (1+ i)) :into digits
     :if (> digits n) :do
     (multiple-value-bind (whole remainder)
         (floor (- n previous) (1+ i))
       (return (aref (write-to-string (+ (expt 10 i) whole)) remainder)))
     :else :do (setf previous digits)))

The idea for implementation is to:

  1. Sum the length of all 1-digit numbers (of which there are $9*10^0$), then sum all 2-digit numbers (of which there are $9*10^1$), 3-digit numbers, of which there are $9*10^2$ and so on. This gives:

$$ N = \sum_{i=0}^m 9\times 10^i \times (i+1) $$

  1. Notice that $x = \lfloor\frac{n - N}{i+1}\rfloor$ will be a positive integer which counts the number of numbers having $m+1$ digits in them.
  2. Finally, after you've already found what number contains your digit, you can find $e$ s.t. $r - e = 10^i + \frac{n - N}{i+1}$, and $e \leq i$ the $e'th$ digit of $x$ is going to be the one you are looking for.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Probably, i + 1 instead of i in step 1? $\endgroup$ – Sungguk Lim Feb 29 '16 at 4:05
  • $\begingroup$ @SunggukLim yup, it should be i +1. $\endgroup$ – wvxvw Feb 29 '16 at 6:44
4
$\begingroup$

The idea here is as follows:

  • The first 9 digits are 123456789.
  • The next 90 pairs of digits are (10)(11)...(99).
  • The following 900 triplets of digits are (100)(101)...(999).
  • And so on.

Given an index $n$, you calculate which group you are (singles, pairs, triplets, ...), then which tuple you belong to and which digit inside the tuple. For example, if $n=28$ then this is digit no. 19 in the second group, which is the first digit of the 10th tuple 19, that is, 1.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.