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

Example:


Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Complete search

Starter code: class Solution:
    def countDigitOne(self, n: int) -> int:
        

Solutions:
class Solution:

	def countDigitOne(self, n):
		(ones, m) = (0, 1)
		while m <= n:
			ones += (n // m + 8) // 10 * m + (n // m % 10 == 1) * (n % m + 1)
			m *= 10
		return ones


class Solution:

	def countDigitOne(self, n):
		if n <= 0:
			return 0
		(q, x, ans) = (n, 1, 0)
		while q > 0:
			digit = q % 10
			q = q // 10
			ans += q * x
			if digit == 1:
				ans += n % x + 1
			elif digit > 1:
				ans += x
			x *= 10
		return ans


class Solution:

	def countDigitOne(self, n):
		(ones, wei) = (0, 1)
		while wei <= n:
			m = int(n / wei) % 10
			if m > 1:
				ones += (int(n / wei / 10) + 1) * wei
			elif m == 1:
				ones += int(n / wei / 10) * wei + n % wei + 1
			else:
				ones += int(n / wei / 10) * wei
			wei *= 10
		return int(ones)


class Solution:

	def countDigitOne(self, n):
		if n <= 0:
			return 0
		(one, m) = (0, 1)
		while m <= n:
			one += (n // m + 8) // 10 * m + (n // m % 10 == 1) * (n % m + 1)
			m *= 10
		return one


class Solution:

	def countDigitOne(self, n):
		if n <= 0:
			return 0
		(counts, length, digits) = (0, len(str(n)), [int(i) for i in str(n)])
		counts = digits[0] * (length - 1) * 10 ** (length - 2) + min(digits[0] - 1, 1) * 10 ** (length - 1) + max(2 - digits[0], 0) * (n - 10 ** (length - 1) + 1) + Solution().countDigitOne(n - digits[0] * 10 ** (length - 1))
		return int(counts)


class Solution:

	def countDigitOne(self, n):
		if n <= 0:
			return 0
		i = 0
		while pow(10, i) <= n:
			i += 1
		if i == 1:
			return 1
		s = n % pow(10, i - 1)
		temp = self.countDigitOne(s)
		t = n // pow(10, i - 1)
		if t > 1:
			temp1 = pow(10, i - 1)
		elif t == 1:
			temp1 = s + 1
		temp2 = t * (i - 1) * pow(10, i - 2)
		return temp + temp1 + temp2