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.

For example:

Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Solution

class Solution {
public:
    int countDigitOne(int n) {
        if ( n <= 0 ) return 0;
        long res = 0, i = 0, d = 1;
        while ( (n/d) != 0 ) {
            long x1 = 2*d- 1, x2 = d - 1;
            res += d*(n/(d*10)) + max(min(n%(d*10), x1) - x2, long(0));
            d *= 10;
        }
        return res;
    }
};

Notes
Count the appearance of 1 in last digit, last but second digit,..., and so on.