Project Euler #32: Pandigital products (C++)
Question
Answer : 45228
Hacker Rank Problem
Solution
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.
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.
Answer : 45228
Hacker Rank Problem
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include <iostream> #include <vector> #include <set> #include <algorithm> int main() { unsigned int N; std::cin >> N; std::vector<unsigned int> digs = {1, 2, 3, 4, 5, 6, 7, 8, 9}; digs.resize(N); std::set<unsigned int> val; do { for(unsigned int Aln = 1; Aln < N; Aln++) { for(unsigned int Bln = 1; Bln < N - Aln; Bln++) { unsigned int Cln = N - Aln - Bln; if(Cln < Aln || Cln < Bln) { break; } unsigned int pos = 0; unsigned int a = 0; for(unsigned int i = 1; i <= Aln; i++) { a *= 10; a += digs[pos++]; } unsigned int b = 0; for(unsigned int i = 1; i <= Bln; i++) { b *= 10; b += digs[pos++]; } unsigned int c = 0; for(unsigned int i = 1; i <= Cln; i++) { c *= 10; c += digs[pos++]; } if((a * b) == c) { val.insert(c); } } } } while(std::next_permutation(digs.begin(), digs.end())); unsigned int sum = 0; for(auto x : val) { sum += x; } std::cout << sum << std::endl; return 0; } |
Comments
Post a Comment