/**
 a b c d e f
 _ _ ^ _ _ _

left ^ right  
        t

00 -- ab-1    000 -- 999   1000;

ab | c == 0    0
   | c == 1    000 -- def  def+1;
   | c > 1     000 -- 999  1000;   (t *= 10 --> t == 1000);
*/
class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if(n == 0) return 0;
        vector<int> numbers;
        while(n) numbers.push_back(n % 10), n /= 10;

        int ans = 0;

        for(int i = numbers.size() - 1; i >= 0; --i)
        {
            int left = 0, right = 0, t = 1;
            for(int j = numbers.size() - 1; j > i; --j) left = left * 10 + numbers[j];
            for(int j = i -1; j >= 0; --j) right = right * 10 + numbers[j], t *= 10;

            ans += left * t;
            if(numbers[i] == 1) ans += right + 1;
            else if(numbers[i] > 1) ans += t;
        }
        return ans;
    }
};