computing count of numbers from 1 to 10 ^ d - 1 , d = 0 a [ 0 ] = 0 ; d = 1 a [ 1 ] = count of numbers from 0 to 9 = 1 d = 2 a [ 2 ] = count of numbers from 0 to 99 = a [ 1 ] * 9 + 10 = 19 d = 3 a [ 3 ] = count of numbers from 0 to 999 = a [ 2 ] * 19 + 100 = 171
int * a = new int [ d + 1 ] ; a [ 0 ] = 0 , a [ 1 ] = 1 ; for ( int i = 2 ; i <= d ; i ++ ) a [ i ] = a [ i - 1 ] * 9 + ceil ( pow ( 10 , i - 1 ) ) ;