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