Question

Formatted question description: https://leetcode.ca/all/233.html

 233	Number of Digit One

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.



Algorithm

This question is actually equivalent to a question to find a pattern. So in order to find the rule, we first enumerate all the numbers containing 1 and count the number every 10

 Number of 1 Numbers with 1 Number range 1 1 [1, 9] 11 10 11 12 13 14 15 16 17 18 19 [10, 19] 1 21 [20, 29] 1 31 [30, 39] 1 41 [40, 49] 1 51 [50, 59] 1 61 [60, 69] 1 71 [70, 79] 1 81 [80, 89] 1 91 [90, 99] 11 100 101 102 103 104 105 106 107 108 109 [100, 109] 21 110 111 112 113 114 115 116 117 118 119 [110, 119] 11 120 121 122 123 124 125 126 127 128 129 [120, 129]

There are only 1 1 within 100 except for 11 ‘1’s between 10-19.

If you don’t consider the 10 extra ‘1’s in the interval [10, 19], then for any two-digit number, the number on the ten’s digit (plus 1) represents the number of occurrences of 1.

Code

Java

• 
public class Number_of_Digit_One {

class Solution {
public int countDigitOne(int n) {
int res = 0;
for (long k = 1; k <= n; k *= 10) {
long r = n / k, m = n % k;
res += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
}
return res;
}
}
}

• Todo

• class Solution(object):
def countDigitOne(self, n):
"""
:type n: int
:rtype: int
"""
m = 1
ones = 0
while m <= n:
r = (n / m) % 10
if r > 1:
ones += m
elif r == 1:
ones += n % m + 1

ones += (n / (m * 10)) * m
m *= 10
return ones