Saturday, December 21, 2013

Number system without 7

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

No comments:

Blog Archive

Followers