public int findNthDigit(int n) {
// For 1, 2 .., 9, return the result directly
if(n <= 9){
return n;
}
int base = 1;
// Determine the range
// 10, 11, ..., 99: 90 * 2 digits in total, base = 2
// 101, 102, 103, ..., 999: 900 * 3 digits in total, base = 3
// ...
while(n > 9 * Math.pow(10, base  1) * base)
{
n = n  9 * (int)Math.pow(10, base  1) * base;
base++;
}
// Now we should find out which number the answer follows. eg. if the input is 15, the answer should follow on number "12", that's the variable number for.
int number = (int)Math.pow(10, base  1) + (n  1) / base;
// Then we should find out which specific in the number "12". that's what index for, for input 15, index = 0
int index = (n  1) % base;
// The answer is the indexth digit of the variable number
return Integer.toString(number).charAt(index)  '0';
}
My JAVA solution beats over 90% with explanation inline


@wangbd This is a math problem, I'm not sure I can explain very clearly. So just an example to help you understand.
Suppose input is14
, then then
is equal to4
after thewhile
part. We should find out the 4th digit in range 10, 11, 12 ..., 99. The 1st, 2nd goes to number10
cause10 = 10 + (1  1)/2
and10 = 10 + (2  1)/2
, the 3rd 4th goes to number11
and so on. Then we can know that the nth should goes toMath.pow(10, base  1) + (n  1) / base
. And similar to the calculation ofindex
.

I guess we can say that the "4th digit in range 10, 11, 12 ..., 99" is really the 3rd digit. because after 9, the index of first digit is 0, and second 1, third 2, and fourth 3... so in order to find its index, we do
(n1)/base
. It is really hard to explain, but this is as close as I can think of. Thank you for your prompt response

while(n > 9 * Math.pow(10, base  1) * base) ===> while(n/base > 9 * Math.pow(10, base  1))
It may be better to use division for n, as for some data the right part could be larger than Integer.
The reason it works here is because Math.pow returns a double type, and when doing comparison, n will be cast to double. But for general question, use n/base will be better.Anyway, nice solution!


public class Solution { public int findNthDigit(int n) { if(n<10) return n; int range=9; int previousRange=0; int countDigits=1; //determine the range of nth digit. 10 to 189 is between 10 and 99, 190 to 2889 is between 100 and 999,etc while(n>range) { previousRange=range; range= range+(int)(9*Math.pow(10,countDigits)*++countDigits); } int value=(npreviousRange1)/countDigits; int index=(npreviousRange1)%countDigits; //get the number String number=Integer.toString((int)Math.pow(10,countDigits1)+value); return number.charAt(index)'0'; } }
I think I have the similar idea as you, and when I test with random input, it works.
However when the test case is 1000000000, it will have "Time Limit Exceeded" error.
any idea which line of code cause it?

@momo52620 if you debug your code in some IDE with input 1000000000, you should find out that when countDigits = 9, the range value
range= range+(int)(9*Math.pow(10,countDigits)*++countDigits)
has a Integer value overflow. You may assign the range to belong
to avoid such problem.