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
  • 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, 2016 at 7:05
  • $\begingroup$ You'll find a lot of references on OEIS. $\endgroup$ Mar 11, 2016 at 21:29

2 Answers 2

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.
$\endgroup$
2
  • $\begingroup$ Probably, i + 1 instead of i in step 1? $\endgroup$ Feb 29, 2016 at 4:05
  • $\begingroup$ @SunggukLim yup, it should be i +1. $\endgroup$
    – wvxvw
    Feb 29, 2016 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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