Write a function named nthDigit that accepts an integer N as a parameter and returns the Nth-from-left digit in the very large integer that would result from the concatenation of the sequence of positive integers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
For example, the call of nthDigit(21) would return 5 because the 21st digit is as follows:
12345678910111213141516...
^
You may assume that the value of N passed is a positive integer and that it is within the range of type int.
Part of the challenge of solving this problem is coming up with an efficient algorithm.
You should not use a string to solve the problem.
Try to come up with an algorithm that will still work even for very large values of N in a reasonable runtime.
