A special country does not use the number 7. Whenever a 7 is encounter, the next possible 
number is used. For example, 7 -> 8, 17 -> 19. Given a number in the country, translate it
into our number. 
Solution:
Obviously, this is a base-9 number system, made of digits 0,1,2,3,4,5,6,8,9, where 8 is
actually 7, and 9 is actually 8. 
If a number is given as d1d2d3...dn, then the translation is:
D1 * 9^(n-1) + D2 * 9^(n-2) + .. + Dn * 9^0, 
where Di = di if di = 0-6, 
Di = di - 1 if di = 8 or 9.
Code verification is done below.
#include <iostream>
using namespace std;
// return true if x contains digit 7.
bool contains7(int x) {
    while (x > 0) {
        int y = x % 10;
        if (y == 7) return true;
        x /= 10;
    }
    return false;
}
void getX(int & x) {
    do {
        ++ x;
    } while (contains7(x));
}
// convert new number system number back to normal number.
int convert_back(int x) {
    int v = 0;
    int base = 1;
    while (x > 0) {
        int y = x % 10;
        if (y == 8 || y == 9) y -= 1;
        v += y * base;
        base *= 9;
        x /= 10;
    }
    return v;
}
int main() {
    int x = 0; // new number system number that ignores 7.
    for (int i = 1; i < 1000; ++ i) {
        getX(x);
        string result = (i == convert_back(x) ? "ok" : "err");
        cout << i << "=> " << x << " " << result << "\t";
        if (result == "err") break;
        if (i % 5 == 0) cout << endl;
    }
    cout << endl;
    return 0;
}
Saturday, December 21, 2013
Subscribe to:
Post Comments (Atom)
 
 
No comments:
Post a Comment