# My O(log(n)) solution in JAVA

• To communicate more clear, I introduce my denotations:

• Digital series N: 1 2 3 4 5 6 7 8 9 1 0 1 1 ...
• Number array X: 1 2 3 4 5 6 7 8 9 10 11 ...
• n represents nth element in N; x represents xth element in X.
• Within the whole digits series, denote the total number of digits between x1 and x2, x1 excluded and x2 included, as D(x1,x2) .

## EQUATION n = location_x(x):

The mathematical equation to calculate the location n of the last digit in number x:

• First, we calculate the maximum value of m, where 10^m is equal or less than x:
• m = Math.floor ( Math.log10(x) )
• Then n = 1 + D(1,10) + D(10,100) + ... + D(10^(m-1), 10^m) + D(10^m, x),
• where D(10^m, x) = (x-10^m)*(m+1)
• and D(10^(k-1), 10^k) = (10^k - 10^(k-1))*k + 1. For example, when k=1, D(1, 10) = (10-1)*1+1 = 11; when k=2, D(10, 100) = (100-10)*2+1 = 181
• So n = 1 + (10 - 1)*1 +1 + (100 -10)*2 +1 + ... + (10^m - 10^(m-1))*m + 1 + (x-10^m)(m+1)
• = 1 + m + [10 -1 + 200 - 20 + 3000 - 300 + ... + m * 10^m - m * 10^(m-1) ] + (x-10^m)(m+1)
• = 1 + m + [ -1 - 10 - 100 - 1000 - ... - 10^(m-1) + m * 10^m ] + (x-10^m)(m+1)
• = 1 + m - [ (1－10^m)/(1-10) + m*10^m ] - m * 10^m + x * (m + 1) -10^m
• = (1 - 10^(m+1))/9 + (1 + m)(x+1)
• In summary, the equation is : n = location_x(x) = (1 - 10^(m+1))/9 + (1 + m)*(x+1) , where m = Math.floor ( Math.log10(x) ).

## ALGORITHM:

Given location n (int n < 2^31), I used binary search to find the corresponding x:

• Init i = 0, j = 3 * 10^8. ( location_x(3 * 10^8) > 2^31, so it is big enough and x will be found within [0,3*10^8])
• In each iteration:
• update x = i + (j-i)/2
• localtion_x_last_digit = location_x(x) ; localtion_x_first_digit = localtion_x_last_digit - total_digits_of_x + 1
• if n in range [ localtion_x_first_digit, localtion_x_last_digit], extract the result digit and return; else if n < localtion_x_first_digit, j=x ; else i = x+1.

## COMPLEXITY:

Theoretically, binary search will be executed less then log(3 * 10^8) = 28.1603872598 < 29 times. But the value of init j is indirectly defined by int n. If n is bigger, then the init of j will be bigger. So it is a log(n) algorithm.

## CODE:

"""

``````public class Solution {

public int num_digit(int x){
int num = 1;
while(x/10>0){
x /= 10;
num++;
}
return num;
}

// For example, digit_val(234, 2) = 2
public int digit_val(int x, long n){
for(long i = n; i>0;i--) x /= 10;
return x%10;
}

// the last digit location of number x : D(x) = (1-10^m)/9 +(m+1)(x+1)
public long[] location_x(int x){
long[] D_x = new long[2];
int m = (int)Math.floor( Math.log10(x) );
D_x[1] =(long)(1 - Math.pow(10,m+1)/9 + (long)(m+1)*(x+1) ) ;
D_x[0] = D_x[1] - num_digit(x) + 1;
return D_x;
}

public int findNthDigit(int n) {
int i=0, j=300000000;// location_x(3*10^9) is bigger than 2^31 => so it is big enough
int x = i + (j-i)/2;
long[] lo_hi = new long[2];
lo_hi = location_x(x);

while(!(n>=lo_hi[0] && n<=lo_hi[1])){
if(n<lo_hi[0]) j = x;
else i = x+1;

x = i + (j-i)/2;
lo_hi = location_x(x);
}
return  digit_val(x, lo_hi[1]-n);
}
}
``````

'""

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.