给定 0 到 10^9 及其倒数之间的所有数字，有多少数字是混合的，奇数和偶数？

Question

下一句是练习题。

我做了这个解决方案。它正在执行从 0 到 10^9 的循环。但它需要很多时间才能被执行。所以，我认为下一步是在数字和它的反面之间的结果中添加一个 hashmap 作为键，保存结果。

但是程序仍然在耗时。我想我可能缺少数学理论或另一种在更短时间内解决时间的方法。

计划：

#include <iostream>
#include <cmath>

using namespace std;

int reverseNumber(int n) {
    int reverse = 0;

    while (n > 0) {
        reverse = reverse * 10;
        reverse += n % 10;
        n = n / 10;
    }

    return reverse;
}

string isNumberEvenOddOrMixed(int n) {
    bool even = false;
    bool odd = false;

    while (n > 0) {
        int rem = n % 10;
        n = n / 10;

        if (rem % 2 == 0)
            even = true;
        else
            odd = true;
    }

    return even && odd ? "Mixed" : (even ? "Even" : "Odd");
}

int main(int argc, const char * argv[]) {
    int even = 0, odd = 0, mixed = 0;

    for (int i = 0; i < pow(10, 9); i++) {
        // Verify if i already exists in the hashmap,
        // if it is, just print the value saved.

        int nReversed = reverseNumber(i);
        int sum = i + nReversed;
        string result = isNumberEvenOddOrMixed(sum);


        if (result == "Even") even++;
        else if (result == "Odd") odd++;
        else mixed++;

        // Save i and nReversed in a hashmap with the result
        // hashmap[i] = result;
        // hashmap[nReversed] = result;

        cout << i << " + " <<  nReversed << " = " << sum << " : " << result << "\n";
    }

    cout << "Even: " << even << "\n";
    cout << "Odd: " << odd << "\n";
    cout << "Mixed: " << mixed << "\n";

    return 0;
}

这些是从 0 到 10^2 的结果。我只是打印出来看看数字之间的关系：

0 + 0 = 0 : Odd
1 + 1 = 2 : Even
2 + 2 = 4 : Even
3 + 3 = 6 : Even
4 + 4 = 8 : Even
5 + 5 = 10 : Mixed
6 + 6 = 12 : Mixed
7 + 7 = 14 : Mixed
8 + 8 = 16 : Mixed
9 + 9 = 18 : Mixed
10 + 1 = 11 : Odd
11 + 11 = 22 : Even
12 + 21 = 33 : Odd
13 + 31 = 44 : Even
14 + 41 = 55 : Odd
15 + 51 = 66 : Even
16 + 61 = 77 : Odd
17 + 71 = 88 : Even
18 + 81 = 99 : Odd
19 + 91 = 110 : Mixed
20 + 2 = 22 : Even
21 + 12 = 33 : Odd
22 + 22 = 44 : Even
23 + 32 = 55 : Odd
24 + 42 = 66 : Even
25 + 52 = 77 : Odd
26 + 62 = 88 : Even
27 + 72 = 99 : Odd
28 + 82 = 110 : Mixed
29 + 92 = 121 : Mixed
30 + 3 = 33 : Odd
31 + 13 = 44 : Even
32 + 23 = 55 : Odd
33 + 33 = 66 : Even
34 + 43 = 77 : Odd
35 + 53 = 88 : Even
36 + 63 = 99 : Odd
37 + 73 = 110 : Mixed
38 + 83 = 121 : Mixed
39 + 93 = 132 : Mixed
40 + 4 = 44 : Even
41 + 14 = 55 : Odd
42 + 24 = 66 : Even
43 + 34 = 77 : Odd
44 + 44 = 88 : Even
45 + 54 = 99 : Odd
46 + 64 = 110 : Mixed
47 + 74 = 121 : Mixed
48 + 84 = 132 : Mixed
49 + 94 = 143 : Mixed
50 + 5 = 55 : Odd
51 + 15 = 66 : Even
52 + 25 = 77 : Odd
53 + 35 = 88 : Even
54 + 45 = 99 : Odd
55 + 55 = 110 : Mixed
56 + 65 = 121 : Mixed
57 + 75 = 132 : Mixed
58 + 85 = 143 : Mixed
59 + 95 = 154 : Mixed
60 + 6 = 66 : Even
61 + 16 = 77 : Odd
62 + 26 = 88 : Even
63 + 36 = 99 : Odd
64 + 46 = 110 : Mixed
65 + 56 = 121 : Mixed
66 + 66 = 132 : Mixed
67 + 76 = 143 : Mixed
68 + 86 = 154 : Mixed
69 + 96 = 165 : Mixed
70 + 7 = 77 : Odd
71 + 17 = 88 : Even
72 + 27 = 99 : Odd
73 + 37 = 110 : Mixed
74 + 47 = 121 : Mixed
75 + 57 = 132 : Mixed
76 + 67 = 143 : Mixed
77 + 77 = 154 : Mixed
78 + 87 = 165 : Mixed
79 + 97 = 176 : Mixed
80 + 8 = 88 : Even
81 + 18 = 99 : Odd
82 + 28 = 110 : Mixed
83 + 38 = 121 : Mixed
84 + 48 = 132 : Mixed
85 + 58 = 143 : Mixed
86 + 68 = 154 : Mixed
87 + 78 = 165 : Mixed
88 + 88 = 176 : Mixed
89 + 98 = 187 : Mixed
90 + 9 = 99 : Odd
91 + 19 = 110 : Mixed
92 + 29 = 121 : Mixed
93 + 39 = 132 : Mixed
94 + 49 = 143 : Mixed
95 + 59 = 154 : Mixed
96 + 69 = 165 : Mixed
97 + 79 = 176 : Mixed
98 + 89 = 187 : Mixed
99 + 99 = 198 : Mixed
Even: 24
Odd: 26
Mixed: 50
Program ended with exit code: 0

Answer 1

这里有几个小的优化思路：

1.

for (int i = 0; i < pow(10, 9); i++)

这个循环每次都在重新计算 10^9。只需执行一次并将其存储在 const 变量中

2.

我会将 "isNumberEvenOddOrMixed" 函数更改为 return 枚举值而不是字符串。它将使您的性能略有提高，而不必比较、创建和销毁字符串。

Answer 2

如果你只需要计算奇数、偶数和混合结果，你应该可以通过计算 1111111192 条记录（大约总数的 1/10）找到结果 [0, 10^9)

解决思路

0到9，全部计算即可。

对于剩余的值，请按以下方式思考。您不需要构建 table，而是使用概念。

设置一个table相同位数的值（令位数为r）
- 大小：9 列 10^(r-1) 行
- 值分布：左上角是该数字部分中最小的，向下时加1，向右时加10^(r-1)

10 20 30 40 50 60 70 80 90

11 21 31 41 51 61 71 81 91

12 22 32 42 52 62 72 82 92

...

...

19 29 39 49 59 69 79 89 99

看这个table，你会观察到任何值的结果都和右上角的结果相同（向上1，向右1） .
在这个意义上，你应该能够看到数字 r table，可以通过查找第一列和最后一列的值的结果来计算计数行，然后为每个计算的结果乘以正确的计数器（点 2 中其对角线上的值数，值在 1 到 9 之间）
- （10 的结果）* 1
- （11 的结果）* 2
- （12 的结果）* 3
- （13 的结果）* 4
- （14 的结果）* 5
- （15 的结果）* 6
- （16 的结果）* 7
- （17 的结果）* 8
- （18 的结果）* 9
- （19 的结果）* 9
- （29 的结果）* 8
- （39 的结果）* 7
- （49 的结果）* 6
- （59 的结果）* 5
- （69 的结果）* 4
- （79 的结果）* 3
- （89 的结果）* 2
- （99 的结果）* 1

计数器分布：左上角为1，向下移动时计数器加1，直到达到9。 1在右下角，向左移动计数器加1。

证明

假设您有一个值 'abcdefg' 并且（'a' 不等于 1 且 'bcdefg' 不等于 0）。在这种情况下，上面table中'abcdefg'的右上位置应该存在。

Rewrite 'abcdefg' as a*10^(r-1) + b*10^(r-2) + c*10^(r-3) + ... + f*10 + g

Reverse of 'abcdefg' is g*10^(r-1) + f*10^(r-2) + e*10^(r-3) + ... + b*10 + a

Calculated value of 'abcdefg' is (a+g)*10^(r-1) + (b+f)*10^(r-2) + (c+e)*10^(r-3) + ... + (f+b)*10 + (g+a)

'abcdefg'右上角的值是'abcdefg' + 10^(r-1) - 1，我们可以写成'a"bcdefg"' where a" = a+ 1 和 g" = g-1

Rewrite 'a"bcdefg"' as a"*10^(r-1) + b*10^(r-2) + c*10^(r-3) + ... + f*10 + g"

Reverse of 'a"bcdefg"' is g"*10^(r-1) + f*10^(r-2) + e*10^(r-3) + ... + b*10 + a"

Calculated value of 'a"bcdefg"' is (a"+g")*10^(r-1) + (b+f)*10^(r-2) + (c+e)*10^(r-3) + ... + (f+b)*10 + (g"+a")

Since g"+a" = g-1 + a+1 = g+a, we have calculated value of 'a"bcdefg"' is (a+g)*10^(r-1) + (b+f)*10^(r-2) + (c+e)*10^(r-3) + ... + (f+b)*10 + (g+a) and is equal to calculated value of 'abcdefg'

这证明计算值将与其右上角元素的计算值相同

给定 0 到 10^9 及其倒数之间的所有数字，有多少数字是混合的，奇数和偶数？

Given all numbers between 0 and 10^9 and its reverse, how many numbers are mixed, odd and even?

java

c++

algorithm

math

analysis