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

例如输入 12，从 1 到 12 这些整数中包含 “1” 的数字有 1，10，11 和 12，其中 “1” 一共出现了 5 次。

样例

输入： 12
输出： 5

参考答案

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for (int i = 1; i <= n; i *= 10) {
            int a = n / i,b = n % i;
            //之所以补8，是因为当百位为0，则a/10==(a+8)/10，
            //当百位>=2，补8会产生进位位，效果等同于(a/10+1)
         count += (a + 8) / 10 * i + ((a % 10 == 1) ? b + 1 : 0);
        }
        return count;
    }
};
//总结一下以上的算法，可以看到，当计算右数第 i 位包含的 X 的个数时：

//取第 i 位左边（高位）的数字，乘以 10i−1，得到基础值 a。
//取第 i 位数字，计算修正值： 
//如果大于 X，则结果为 a+10i−1。
//如果小于 X，则结果为 a。
//如果等 X，则取第 i 位右边（低位）数字，设为 b，最后结果为 a+b+1。