<p>Given an integer <code>n</code>, count <em>the total number of digit </em><code>1</code><em> appearing in all non-negative integers less than or equal to</em> <code>n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 13
<strong>Output:</strong> 6
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:

    int factorial(int D) {
        if(D == 0)
            return 1;

        int prod1 = 1;
        for(int k=1; k <= D; k++)
            prod1 *= k;
        
        return prod1;
    }

    int solve(int D) {

        if(D == 1)
            return 1;

        int count = 0;
        for(int i=1; i <= D; i++) {
            count += i*(factorial(D)/(factorial(i)*factorial(D-i))*pow(9,D-i));
        }

        return count;

    }

    int countDigitOne(int n) {
        if(n == 0)
            return 0;

        if(n <= 9)
            return 1;

        int num = n;
        int digits = 0;

        vector<int> digs;

        while(num > 0) {
            digs.push_back(num%10);
            num /= 10;
            digits++;
        }

        reverse(digs.begin(),digs.end());
        vector<int> onesOnRight(digs.size(),0);

        int onesCount = 0;
        for(int i=0; i < digs.size(); i++) {
            onesOnRight[i] = onesCount;
            if(digs[i] == 1)
                onesCount++;
        }
 
        int ans = 1; // For single digits
        for(int i=2; i <= digits-1; i++) {
            ans += 9*solve(i-1); // For counting all ones occurign in all place excerp letmost
            ans += 1*pow(10,i-1); // Counting leftmost occurrences
        }

        cout << ans << endl;
        // for(auto ka : digs)
        //     cout << ka << " ";
        // // For exactly 

        int digsOnRight = 1;
        ans += onesOnRight[digs.size()-1]*(digs[digs.size()-1]+1);
        if(digs[digs.size()-1] > 0) {
            ans++;
        }
        cout << ans << endl;
        for(int i=digs.size()-2; i >= 0; i--) {
            int d = digs[i];
            if(d == 0) {
                digsOnRight++;
                continue;
            }
            
            if(i != 0) {

                if(d == 1) {
                ans += onesOnRight[i]*(1)*pow(10,digsOnRight) + solve(digsOnRight);
                }
                else {
                ans += onesOnRight[i]*(d-1)*pow(10,digsOnRight) + solve(digsOnRight)*(d-1); // Count for all non ones on curr digits
                }
                if(d > 1)
                    ans += (onesOnRight[i]+1)*(pow(10,digsOnRight)) + solve(digsOnRight);

            }
            else {
                ans += onesOnRight[i]*(max(0,d-2))*pow(10,digsOnRight) + solve(digsOnRight)*(max(0,d-2));

                if(d >= 2)
                    ans += (onesOnRight[i]+1)*(pow(10,digsOnRight)) + solve(digsOnRight);

            }
            cout << "Hello " << ans << endl;
            digsOnRight++;
        }


        return ans;

    }
};
7700