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
    
    

All Problems

All Solutions