# 233. 数字 1 的个数

int countDigitOne(int n){
    if(n==0) return 0;
    if(n==1000000000) return 900000001;
    int * arr = (int *)malloc(sizeof(int) * 9);
    int total[9] = {1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000};
    int minus[9] = {0, 1,  20,  300,  4000,  50000,  600000,  7000000,  80000000 };
    int adds[9] =  {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 0        };
    int arrLen = 0;
    while(n)
    {
        arr[arrLen++] = n % 10;
        n /= 10;
    }
    int i = arrLen -1;
    int result = (total[i] - minus[i] * (9 - arr[i]));
    for(i--; i>=0; --i)
    {
        if (arr[i+1] == 1)
        {
            int j;
            for(j = 0; j<9; j++)
            {
                minus[j] += adds[j];
            }
        }
        result -= minus[i] * (9 - arr[i]);
        if(arr[i] == 0)
        {
            result -= adds[i];
        }
    }
    free(arr);
    return result;
}