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

233 - Number of Digit One

Question

Algorithm

Code

All Problems

All Solutions