DevClub.eu programming challenge (Oct. 2012)

NatNumSequence.java

package eu.devclub;

import java.util.*;

public class NatNumSequence {

    public static int getNthDigit(long index) {
        if(index < 1) throw new IllegalArgumentException( "Not a natural number" );
        if(index < 10 ) return (int) index;
        
        long currentLength = 0;
        long prevLength = 0;
        int digits = 0;
        while(currentLength < index) {
            prevLength = currentLength;
            currentLength += getNdigitNumSum( ++digits );
        }

        return findByIndex(prevLength, digits, index);
    }
    
    private static long getNdigitNumCount(int n) {
        long bottom = tenPower(n-1);
        long top = bottom*10;
        return top-bottom;
    }
    
    private static long getNdigitNumSum(int n) {
        return n*getNdigitNumCount( n );
    }
    
    private static int findByIndex(long low, int digits, long index) {
    	long base = tenPower(digits-1);
    	long diff = index-(low+1);
    	long integral = diff / digits;
    	long number = base + integral;
    	long offset = low + (integral+1)*digits - index;
    	return getNthDigitFromRight(number, offset);
    }
    
    //index of the first position from right is 0
    private static int getNthDigitFromRight(long num, long pos) {
    	return (int) ( (num / tenPower(pos) ) % 10 );
    }
    
    private static HashMap<Long, Long> tenPowers = new HashMap<Long, Long>();
    
    private static long tenPower(long pow) {
    	Long result;
    	if((result = tenPowers.get(pow)) == null) {
    		result = (long) Math.pow( 10, pow );
    		tenPowers.put(pow, result);
    	}
    	return result;
    }
    
    public static void main( String[] args ) {
        long[] idxs = new long[] {1, 7, 10, 17, 189, 1000000005000000000L};
        for ( long i : idxs ) {
        	long start = System.nanoTime();
            System.out.println("f(" + i + ")=" + getNthDigit( i ) + " computed in " + + (System.nanoTime()-start) + "ns.");
        }
    }
}