public class NumberOf1Between1AndN {

    /*

     *输入一个整数n,求从1到n这N个十进制表示中1出现的次数

     *以5位数说明：

     *

     *当百位上数字是0时：如：20099的1出现的次数为100-199,1100-1199，。。。，19100-19199共20*100次，即为高位数*100

     *当百位上数字是1时：如：20134的1出现的次数为100-199,1100-1199，。。。，19100-19199共20*100次，

     *    和低位数字出现数字34+1次，即21100-21134，共20*100+（34+1）

     *当百位上数字大于1时：如20233的1出现的次数为100-199,1100-1199，。。。，19100-19199,20100-20199共21*100，即为（高位数+1）*100；

     *其它各位同理，不再详述

     */

    public long CountOne(long n)

    {

        long count = 0;

        long i = 1;

        long current = 0,low = 0,high = 0;

        while((n / i) != 0)

        {

            current = (n / i) % 10;//当前位是多少

            high = n / (i * 10);//得到高位数

            low = n - (n / i) * i;//低位数

            if (current > 1)

                count = count + (high + 1) * i;

            else if (current == 0)

                count = count + high * i;

            else if(current == 1)

                count = count + high * i + low + 1;

            i = i * 10;

        }

        return count;

    }

    public static void main(String[] args){

        long num = 12;

        long mm = System.currentTimeMillis();

        System.out.println(new NumberOf1Between1AndN().CountOne(num));

        System.out.println("m2 " + (System.currentTimeMillis() - mm));

    }

}