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

Question

The next statement is the problem for an exercise.

I did this solution. It's executing a loop from 0 to 10^9. But it's taking many time for being executed. So, the next step which I thought is add a hashmap into the result between the number and its reverse as keys, saving the result.

But the program is still consuming time. I guess I'm missing maybe a math theory or another approach to solve time in less time.

Program:

#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;
}

These are the results from 0 to 10^2. I just printed to see the relationship between the numbers:

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

`for (int i = 0; i < pow(10, 9); i++) ` -- You are calling `pow()` multiple times for no reason whatsoever. In addition, it returns a `double`, not an int, plus `pow` is not guaranteed to give you an exact answer, even if you're using integer. 3 strikes, your out. Just put `for (int i = 0; i < 1000000000; ++i)` or similar. — PaulMcKenzie, Jun 27 '16 at 04:00
Also, you have multiple tags. Please choose a language. In any event, why is your function that determines what type of number it is returning a `string`? That takes time constructing and destroying that returned string. Just return an `int` denoting the type, not a string. You're also comparing strings to "Even", "Odd", etc. taking up time. There should be **no** string usage at all in this program, except to output the results. — PaulMcKenzie, Jun 27 '16 at 04:09
Also, in your function to determine if the number is odd or even, if both odd and even flags are `true`, return right away that the number is mixed. There is no need to keep looping through the number if both flags happen to be true. — PaulMcKenzie, Jun 27 '16 at 04:25
@PaulMcKenzie: That first reason is premature optimization (why optimize manually what a compiler optimizes automatically?), the last is rather theoretical as `double` has enough precision. — MSalters, Jun 27 '16 at 07:08
you need to print all 10^9 result out ? or just the count of odd , even , mixed result? — shole, Jun 27 '16 at 08:37
@oscar.fimbres why i am asking is that, if you want to speed up, then printing out all solution is impossible as I/O time itself is already O(10^9). While if you only need to count the result, I am thinking there maybe some DP solution / combinatorics can help — shole, Jun 28 '16 at 01:04
@oscar.fimbres Also I do not understand why this question has so many downvotes..I think it is a not-so-easy problem and you have posted your code, elaborate on the question, etc.... — shole, Jun 28 '16 at 01:06
@shole yeah, also I was thinking that might be an performance issue (printing). What do you mean when you say combinatorics or DP? — oscar.fimbres, Jun 28 '16 at 01:09
@oscar.fimbres hard to explain in comments, you can just Google them. DP stands for dynamic programming (not disney princess). — shole, Jun 28 '16 at 01:13
@oscar.fimbres You don't need to check all possible value, but part of them — hk6279, Jun 30 '16 at 02:12

score 1 · Answer 1 · answered Jun 27 '16 at 04:13

1

Here are a couple of small optimisation ideas:

1.

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

This loop is recalculating 10^9 every time. Just do it once and store it in a const variable

2.

I would change the "isNumberEvenOddOrMixed" function to return an enumeration value instead of a string. It will gain you a small increase in performance not having to compare, create and destroy strings.

answered Jun 27 '16 at 04:13

bennji_of_the_overflow

1,123
5
13

1

The `pow` doesn't even need to be called at all, plus it has the potential to give wrong results. See [this question and answer](http://stackoverflow.com/questions/25678481/why-pown-2-return-24-when-n-5/25678721#25678721) – PaulMcKenzie Jun 27 '16 at 04:14
Yes, you're right. I didn't really mean to imply that he should use pow at all - just that he should calculate the result before hand, but I can see I wasn't clear. – bennji_of_the_overflow Jun 27 '16 at 06:30

hk6279 · Accepted Answer · 2016-06-30T02:08:24.340

If you just need to count odd, even and mixed result, you should be able to find the result by calculate 1111111192 records (about 1/10th of total) for [0, 10^9)

Solution Idea

For 0 to 9, just calculate it all.

For remaining values, think as below. you don't need to build the table, but use the concept.

Setup a table for value of same number of digits (let number of digit be r)
- size: 9 column with 10^(r-1) row
- value distribution: Top left corner is the smallest of that digit part, plus one when moving down, plus 10^(r-1) when moving right

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

Looking at this table, you will observe the result of any value will be same as the result as the one on its top right position (upward by 1 and right by 1).
In this sense, you should be able to see for digit r table, the count can be calculated by looking up result of values on first column and last row and then for each result calculated times a correct counter (number of values in its diagonal in point 2, values between 1 to 9)
- (result of 10) * 1
- (result of 11) * 2
- (result of 12) * 3
- (result of 13) * 4
- (result of 14) * 5
- (result of 15) * 6
- (result of 16) * 7
- (result of 17) * 8
- (result of 18) * 9
- (result of 19) * 9
- (result of 29) * 8
- (result of 39) * 7
- (result of 49) * 6
- (result of 59) * 5
- (result of 69) * 4
- (result of 79) * 3
- (result of 89) * 2
- (result of 99) * 1

counter distribution: 1 at top left, increase counter by 1 when moving down till 9 is reached. 1 at bottom right, increase counter by 1 when moving left.

Prove

Assume you have a value 'abcdefg' and ('a' not equal to 1 and 'bcdefg' not equal to 0). Under this condition, top right position of 'abcdefg' in above table should exist.

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)

The value in top right position of 'abcdefg' is 'abcdefg' + 10^(r-1) - 1. We can write it as 'a"bcdefg"' where a" = a+1 and 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'

This prove that the calculated value will be same as the calculated value of its top right element

Thanks for wise response. I'm surprised how you quickly could arrive to this good solution. I did the sample with r = 2. Just for the case when r = 3, so if I understand well, it's necessary to calculate the numbers from 100 to 199 (incrementing 1) and then 199 (incrementing 100), right? — oscar.fimbres, Jun 30 '16 at 02:16
@oscar.fimbres Yes, it is correct for the case when r=3.One simple way is to generate some number of continuous sample and then look for a repeating pattern. — hk6279, Jun 30 '16 at 06:18

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

2 Answers2