Repository navigation
Expand file tree
/
Copy pathNumberOfDigitOne.cpp
More file actions
74 lines (68 loc) · 2.53 KB
/
Copy pathNumberOfDigitOne.cpp
File metadata and controls
74 lines (68 loc) · 2.53 KB
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Source : https://leetcode.com/problems/number-of-digit-one/
// Author : Hao Chen
// Date : 2015-07-17
/**********************************************************************************
*
* Given an integer n, count the total number of digit 1 appearing in all non-negative
* integers less than or equal to n.
*
* For example:
* Given n = 13,
* Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
*
* Beware of overflow.
*
**********************************************************************************/
/*
* The idea is:
*
* 1) seprate the n to two parts. considering n is `abc`
*
* 2) at first, we seprate it to `ab` & `c`, then,
* c == 0, the # of `1` appears in uints is "ab * 1"
* c == 1, the # of `1` appears in units is "ab * 1 + 0 + 1" (0 means the number after `c`)
* c > 1 , the # of `1` appears in units is "(ab+1)*1"
*
* 3) at second, we seprate it to `a` & `bc`, then,
* b == 0, the # of `1` appears in tens is "a * 10"
* b == 1, the # of `1` appears in tens is "a * 10 + c + 1" (`c` means the number after `b`)
* b > 1 , the # of `1` appears in tens is "(a+1)*10"
*
* 4) at thrid, we seprate it to `` & `abc`, then,
* a == 0, the # of `1` appears in tens is "0 * 100" ( 0 menas the number before `a`)
* a == 1, the # of `1` appears in tens is "0 * 100 + bc + 1" (`bc` means the number after `a`)
* a > 1 , the # of `1` appears in tens is "(0+1)*100"
*
*
* For some examples:
* 0) n = 5, we have (0+1)*1 = 1 digit 1
* 1) n = 53, we have (5+1)*1 + (0+1)*10 = 16 digit 1
* 2) n = 20, we have (2*1) + (0+1)*10 = 12 digit 1
* 3) n = 21, we have (2*1+0+1) + (0+1)*10 = 13 digit 1
* 4) n = 13, we have (1+1)*1 + (0*10+3+1) = 6 digit 1
* 5) n = 109, we have (10+1)*1 + (1*10) + (0*100 + 09 + 1) = 31 digit 1
*
* Converting the ideas to code as below:
*
*/
class Solution {
public:
int countDigitOne(int n) {
long long base=1, left=n, right=0, currDigit=0;
int numOfOne = 0;
while(left>0) {
currDigit = left % 10;
left = left/ 10;
if (currDigit == 0) {
numOfOne += (left * base);
}else if (currDigit == 1) {
numOfOne += (left * base + right + 1);
}else {
numOfOne += ((left+1)*base);
}
right = right + currDigit * base;
base *= 10;
}
return numOfOne;
}
};