整数中1出现的次数

描述

求出1~ 13的整数中1出现的次数,并算出100~ 1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

先使用数学归纳法求出各位上1的次数公式。

个位

个位上的 1 ，是每隔10出现一次。如：11、21、31。那么可得出 count = n/10,但对于数 22, 22/10 = 2，余数部分出现的1未被统计，所以需要需要判断是否存在余数。

最终得出个位公式为：n/10 + (n%10!=0 ? 1 : 0)

十位

同理可得，十位出现1是每隔100出现十次，如：10、11...19。即(n/100) * 10，同时也需要考虑余数部分，余数大于 19 则加10，小于10则不加，之间则加上余数 - 9, 同时设余数为k。

最终得出十位公式为：(n / 100) * 10 + (if(k > 19) 10 else if(k < 10) 0 else k - 10 + 1)

百位

推理同上，公式为：(n / 1000) * 100 + (if(k >199) 100 else if(k < 100) 0 else k - 100 + 1)

i位

到这里，就可以根据以上公式得出每位的归纳式了，如下：

count(i) = (n / (i * 10)) * i + (if(k > i * 2 - 1) i else if(k < i) 0 else k - i + 1)

• i： 第几位
• k: 余数 = n%(i*10)

总次数

得出了每一位的1的次数，Sum = count(1) + ....+ count(i)

实现如下：

public int NumberOf1Between1AndN_Solution(int n) {
     if(n <= 0)
       return 0;
         int count = 0;
         for(long i = 1; i <= n; i *= 10){
             long diviver = i * 10;          
             count += (n / diviver) * i + Math.min(Math.max(n % diviver - i + 1, 0), i);
        }
         return count;
    }