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