题目:从0到n数字中2的个数

思路:

1、暴力法：

从0到n,遍历每一个数字，对每一个数字的每一位进行判断

2、通过数学规律优化

思路：

计算十位数字为2的数字个数：

四位数字：【a】【b】【d】【c】

1、 当d<2 时 数字最大为 ab19，十位数字为2 的情况为

高位 <(ab-1) xy<=ab-1>=0

eg: xy20 xy21 xy22 xy23 xy24 xy25 xy26 xy27xy28 xy29

十位2的个数：(ab-1+1) *10^(2-1)

2、当 d=2时，数字最大为 ab29, 最接近第一种情况的数字为ab20

ab20 的 十位2 的个数比 ab1x 多1 ，每比ab20 多一就多一个十位为2的数字;

十位2的个数：ab*10 + 1+c

3、当d>2,时第二种情况之后的最大值之后，就是ab30+,之后十位不会出现2。

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
#include <iostream>

int countTwos(int n) {
    int count = 0;
    for (long long digit = 1; n / digit > 0; digit *= 10) {
        int high = n / (digit * 10);
        int cur = (n / digit) % 10;
        int low = n % digit;

        if (cur < 2) {
            count += high * digit;
        } else if (cur == 2) {
            count += high * digit + low + 1;
        } else {
            count += (high + 1) * digit;
        }
    }
    return count;
}

int main() {
    int n;
    std::cout << "Enter a number n: ";
    std::cin >> n;

    int result = countTwos(n);
    std::cout << "Number of times 2 appears from 0 to " << n << " is: " << result << std::endl;

    return 0;
}