面试题43

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

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

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：

• 1 <= n < 2^31

注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

Solutions

1. count by digit

class Solution {
public:
    int countDigitOne(int n) {
        long res = 0;
        for (long num = 1; num <= n; num *= 10) {
            long base = num * 10; 
            res += (n / base) * num + min(max((n % base) + 1 - num, 0l), num);
        }

        return res;
    }
};