233. Number of Digit One

233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

-----------------------
以百位上1的个数举例，3种情况：
55023 -> 55 * 100
55123 -> 55 * 100 + 23  + 1
55523 -> (55 + 1) * 100

class Solution {
    public int countDigitOne(int n) {
        long rt = 0;
        for (long i = 1; i <= n; i *= 10) {
            long first = n / i, second = n % i;
            long mid = first % 10;
            if (mid == 0) {
                rt += first / 10 * i;
            }else if (mid == 1) {
                rt += first / 10 * i + second + 1;
            }else {
                rt += (first / 10 + 1) * i;
            }
        }
        
        return (int)rt;
    }
}