Quoting projecteuler:
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
The problem is quite straight forward: For all permutations of 123456789 check if you can form a pandigital product. If so, add the product to a unique set. The first five digits of each permutation are reserved to form the two factors, the last four for the resulting product.
The STL offers all the neccessary tools: std::next_permutation and std::set. Obviously, the implementation did not aim for good design.
bool check_product(int x1, int x2, int res) {
return (x1*x2) == res;
}
template <typename t>
int get_int_from_array(T* begin, T* end) {
--end;
--begin;
int res = 0;
for (int n = 1; end != begin; --end, n *= 10) {
res += n*(*end);
}
return res;
}
void get_set_of_pandigital_products(int* begin, int* end, std::set<int>& prods) {
int n_digits = end-begin;
int n_max = 5;
int x1, x2, res;
do {
for (int i = 0; i < n_max-1; ++ i) {
x1 = get_int_from_array(begin, begin+i);
x2 = get_int_from_array(begin+i, begin+n_max);
res = get_int_from_array(begin+n_max, begin+n_digits);
if (check_product(x1, x2, res)) {
prods.insert(res);
}
}
} while (std::next_permutation(begin, end));
}
As usual, the code can be found on github.
No comments:
Post a Comment