Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/233.html
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example 1:
Input: n = 13 Output: 6
Example 2:
Input: n = 0 Output: 0
Constraints:
0 <= n <= 109
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
-
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; } } } ############ class Solution { private int[] a = new int[12]; private int[][] dp = new int[12][12]; public int countDigitOne(int n) { int len = 0; while (n > 0) { a[++len] = n % 10; n /= 10; } for (var e : dp) { Arrays.fill(e, -1); } return dfs(len, 0, true); } private int dfs(int pos, int cnt, boolean limit) { if (pos <= 0) { return cnt; } if (!limit && dp[pos][cnt] != -1) { return dp[pos][cnt]; } int up = limit ? a[pos] : 9; int ans = 0; for (int i = 0; i <= up; ++i) { ans += dfs(pos - 1, cnt + (i == 1 ? 1 : 0), limit && i == up); } if (!limit) { dp[pos][cnt] = ans; } return ans; } } -
class Solution: def countDigitOne(self, n: int) -> int: @cache def dfs(pos, cnt, limit): if pos <= 0: return cnt up = a[pos] if limit else 9 ans = 0 for i in range(up + 1): ans += dfs(pos - 1, cnt + (i == 1), limit and i == up) return ans a = [0] * 12 l = 1 while n: a[l] = n % 10 n //= 10 l += 1 return dfs(l, 0, True) ############ 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 -
class Solution { public: int a[12]; int dp[12][12]; int countDigitOne(int n) { int len = 0; while (n) { a[++len] = n % 10; n /= 10; } memset(dp, -1, sizeof dp); return dfs(len, 0, true); } int dfs(int pos, int cnt, bool limit) { if (pos <= 0) { return cnt; } if (!limit && dp[pos][cnt] != -1) { return dp[pos][cnt]; } int ans = 0; int up = limit ? a[pos] : 9; for (int i = 0; i <= up; ++i) { ans += dfs(pos - 1, cnt + (i == 1), limit && i == up); } if (!limit) { dp[pos][cnt] = ans; } return ans; } }; -
func countDigitOne(n int) int { a := make([]int, 12) dp := make([][]int, 12) for i := range dp { dp[i] = make([]int, 12) for j := range dp[i] { dp[i][j] = -1 } } l := 0 for n > 0 { l++ a[l] = n % 10 n /= 10 } var dfs func(int, int, bool) int dfs = func(pos, cnt int, limit bool) int { if pos <= 0 { return cnt } if !limit && dp[pos][cnt] != -1 { return dp[pos][cnt] } up := 9 if limit { up = a[pos] } ans := 0 for i := 0; i <= up; i++ { t := cnt if i == 1 { t++ } ans += dfs(pos-1, t, limit && i == up) } if !limit { dp[pos][cnt] = ans } return ans } return dfs(l, 0, true) } -
public class Solution { public int CountDigitOne(int n) { if (n <= 0) return 0; if (n < 10) return 1; return CountDigitOne(n / 10 - 1) * 10 + n / 10 + CountDigitOneOfN(n / 10) * (n % 10 + 1) + (n % 10 >= 1 ? 1 : 0); } private int CountDigitOneOfN(int n) { var count = 0; while (n > 0) { if (n % 10 == 1) ++count; n /= 10; } return count; } }