The problem is straightforward: given a positive integer n, count the total number of times the digit 1 appears in all numbers from 1 to n.
For example, for the number 12312, global count += 2 because 1 appears twice. Given input n, we need to compute this for all numbers from 1 to n.
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
| int VerifyCountOneNumberAns(int n)
{
int ans = 0;
for (int i = 1; i <= n; i++)
{
int tmp = i;
while(tmp)
{
if (1 == tmp%10) ans++;
tmp /= 10;
}
}
return ans;
}
int CountOneNumber(int n)
{
if (n == 0)
return 0;
if (n < 10)
return 1;
vector<int> vNumber;
vNumber.clear();
int tmp = n;
while(tmp)
{
vNumber.push_back(tmp%10);
tmp /= 10;
}
int count = 0;
int vSize = vNumber.size();
count = (vSize - 1) * vNumber[vSize - 1] * (int)pow(10.0, (int)(vSize - 2));
if (vNumber[vSize - 1] > 1)
{
count += (int)pow(10.0, (int)(vSize - 1));
}
else
{
count += n - vNumber[vSize - 1] * (int)pow(10.0, vSize - 1) + 1;
}
count += CountOneNumber(n - vNumber[vSize - 1] * (int)pow(10.0, vSize - 1));
return count;
}
int main()
{
vector<int> ids;
for (int i = 1; i <= 10000; i++)
{
int count = CountOneNumber(i);
int ans = VerifyCountOneNumberAns(i);
if (ans != count)
cout << i << '\t' << ans << '\t' << count << endl;
}
return 0;
}
|
The code includes a verification function whose correctness is beyond doubt. The problem also provides a recursive approach, which has acceptable time complexity – it should be proportional to the number of digits.
PS: I’m clearly not great at math; this was quite a struggle. But my logic still works well…