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