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

&nbsp;
Example 1:

Input: n = 13
Output: 6


Example 2:

Input: n = 0
Output: 0


&nbsp;
Constraints:


	0 &lt;= n &lt;= 109


class Solution:
    def countDigitOne(self, n: int) -> int:
        num = str(n)[::-1]
        count = 0
        for i in range(len(num)-1, -1, -1):
            pv = 10**i # placevalue
            # mulitplicity of current digit (how many times it will be repeated)
            mul = n//(pv*10)
            rem = n % pv # remainder of current place value
            count += mul * pv # count for number of times 1 occurs in this place when the current digit is considered to be less than 1
            # if the current digit is greater than 1 then additional number of 1's are added to the count (equivalent to the place value)
            if num[i] > '1':
                count += pv
            # if the current digit is equal to 1 then additional number of 1's are added to the count (equivalent to the number modded by the current place value)
            if num[i] == '1':
                count += rem + 1
        return count
  class Solution {
	int max(int a, int b){
		if(a>b)
			return a;
		else
			return b;
	}

	int min(int a, int b){
		if(a>b)
			return b;
		else
			return a;
	}

	public int countDigitOne(int n) {
		int c = 0;
		for(int i=1; i<=n; i*=10){
			int divider = i*10;
			c += (n/divider)*i + min(max((n%divider -i + 1), 0),i);
		}
		return c;
	}
}

// T.C.  - O(log n)
class Solution {
public:
	int countDigitOne(int n) {
		int c = 0;
		for(int i=1; i<=n; i++){
			string s = to_string(i);
			c += count(s.begin(), s.end(), '1');
		}
		return c;
	}
};

// T.C. --> O(n * log(n))
// S.C. --> O(log(n))
var countDigitOne = function(n) {
    if(n <= 0) return 0;
    if(n < 10) return 1;
    var base = Math.pow(10, n.toString().length - 1);
    var answer = parseInt(n / base);
    return countDigitOne(base - 1) * answer + (answer === 1 ? (n - base + 1) : base) + countDigitOne(n % base);
};
Number of Digit One