My O(log(n)) solution in JAVA


  • 0

    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);
    }
    }
    

    '""


Log in to reply
 

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