NUMBER_OF_DIGIT_ONE

class Solution {
public:
    int countDigitOne(int n) {
        /*
            2229
            1029, 1000 - 1029
            1 -29
            1000 - 1029 - 30 1's
            [1 - 999] + 0
            2 * f(999) + divisor + remainder
            2 * something + 1000 + 229
            2200
            2 * f(999) + 1000 + rem = 0;
            f(9) = 1;
            f(99) = 10*f(9) + 9 + 1

        */
        if(n <= 0) {
            return 0;
        }
        unordered_map<long, long> mp;
        mp[9] = 1;
        //9,99,999,......
        for(long i = 9; i < 2 * pow(10,9); i = 10*i + 9) {
            mp[10*i + 9] = 10*mp[i] + i + 1;
        }
        int tp = n;
        int divisor = 1;
        while(tp/10) {
            tp/=10;
            divisor *= 10;
        }
        int rem = n % divisor;
        int ans = 0;
        int first = (n/divisor);
        ans = ans + first * mp[divisor-1];

        if(first > 1) {
            ans += divisor;
        }
        if(first == 1) {
            ans += rem + 1;
        }
        ans += countDigitOne(rem);
        return ans;
    }
};