<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 countDigitOne(int n) {  
        long long count = 0;  
        long long factor = 1; // This represents the current digit place (1, 10, 100, ...)  
        
        while (factor <= n) {  
            long long lowerNumbers = n - (n / factor) * factor; // Numbers lower than the current digit  
            long long currentDigit = (n / factor) % 10; // Current digit  
            long long higherNumbers = n / (factor * 10); // Numbers higher than the current digit  
            
            // Count the occurrences of '1' based on the current digit  
            if (currentDigit == 0) {  
                count += higherNumbers * factor;  
            } else if (currentDigit == 1) {  
                count += higherNumbers * factor + lowerNumbers + 1;  
            } else {  
                count += (higherNumbers + 1) * factor;  
            }  
            
            factor *= 10; // Move to the next digit place  
        }  
        
        return count;  
    }  
};
7300