class Solution {
public:
    int countDigitOne(int n) {
        if(n<=0)return 0;
        if(n<10)return 1;
        int res=0;
        
        vector<int>A;
        A.push_back(1l);
        int mul=10;
        
        for(int i=1;i<9;i++){
            int sum=A[A.size()-1]*10+mul;
            A.push_back(sum);
            mul*=10;
        }
        
        string s=to_string(n);
        int cnt=s.size()-1;
       
        int mod=1;
        for(int i=0;i<cnt;i++){
            mod*=10;
        }
        
        for(int i=0;i<s.size();i++){
            int d=s[i]-'0';
            
            if(i==s.size()-1){
                if(d>0)res++;
                break;
            }
            
            if(d==1){
                res+=((n)%mod+1+A[cnt-1]);    
            }else if(d>1){
                res+=(mod+(d)*A[cnt-1]);
            }  
            mod/=10;
            cnt--;
        }
        
        return res;
    }
};