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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityThis 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.
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:
$$ N = \sum_{i=0}^m 9\times 10^i \times (i+1) $$
The idea here is as follows:
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.