Problem Detail: 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.
Asked By : Sungguk Lim
Answered By : wvxvw
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:
- 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 9times 10^i times (i+1) $$
- Notice that $x = lfloorfrac{n – N}{i+1}rfloor$ will be a positive integer which counts the number of numbers having $m+1$ digits in them.
- 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/53726
