blob: f2888cddd67a920fbf80d2fd9fb78b20a3674164 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
// 233. Number of Digit One
#include "leetcode.h"
/*
* given an integer 'n', count the total number of digit 1 appearing in all
* non-negative integers less than or equal to n
*/
int countDigitOne(int n) {
if (n <= 0)
return 0;
if (n < 10)
return 1;
long ctx = 10, ctx_cnt = 1;
while (n >= ctx * 10) {
ctx_cnt *= 10 + ctx;
ctx *= 10;
}
int ans = ctx_cnt;
if (n >= 2 * ctx) {
ans += ans * 2 + ans * (n / ctx - 2) + ctx - ans;
int low_n = countDigitOne(n % ctx);
ans += low_n;
} else {
int low_n = countDigitOne(n - ctx);
ans += low_n * 2 + (n - (ctx - 1)) - low_n;
}
return ans;
}
int main() {
printf("%d\n", countDigitOne(13)); // expect: 6
printf("%d\n", countDigitOne(0)); // expect: 0
}
|