Pandigital products | Project Euler | Problem #32
URL to the problem page: https://projecteuler.net/problem=32
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.
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.
#include <iostream>
using namespace std;
int finddigits(int a) {
int cnt = 1;
while (a >= 10) {
a /= 10;
cnt++;
}
return cnt;
}
int power(int a, int b) {
int result = 1;
for (int i = 0; i < b; i++) {
result *= a;
}
return result;
}
int main()
{
int i, j, a, b, n = 0, cnt, cnt2 = 0, result[200] = { 0 }, number, digitnumbers[3] = { 0 }, sum2, sum = 0;
for (i = 100; i < 10000; i++) {
for (j = 1; j < 1000; j++) {
cnt2 = 0;
digitnumbers[0] = finddigits(i);
digitnumbers[1] = finddigits(j);
number = i * j;
digitnumbers[2] = finddigits(number);
sum2 = digitnumbers[0] + digitnumbers[1] + digitnumbers[2];
if (sum2 != 9) {
continue;
}
int* digits0 = new int[digitnumbers[0]];
for (a = digitnumbers[0]; a > 0; a--) {
digits0[a - 1] = (i % power(10, a)) / (power(10, (a - 1)));
}
int* digits1 = new int[digitnumbers[1]];
for (a = digitnumbers[1]; a > 0; a--) {
digits1[a - 1] = (j % power(10, a)) / (power(10, (a - 1)));
}
int* digits2 = new int[digitnumbers[2]];
for (a = digitnumbers[2]; a > 0; a--) {
digits2[a - 1] = (number % power(10, a)) / (power(10, (a - 1)));
}
int* digits = new int[sum2];
for (a = 0, b = 0; b < digitnumbers[0]; a++, b++) {
digits[a] = digits0[b];
}
for (a = digitnumbers[0], b = 0; b < digitnumbers[1]; a++, b++) {
digits[a] = digits1[b];
}
for (a = (digitnumbers[0] + digitnumbers[1]), b = 0; b < digitnumbers[2]; a++, b++) {
digits[a] = digits2[b];
}
for (b = 1; b < 10; b++) {
cnt = 0;
for (a = 0; a < sum2; a++) {
if (digits[a] == b) {
cnt++;
}
}
if (cnt != 1) {
cnt2++;
break;
}
}
if (cnt2 == 0) {
cout << i << " x " << j << " = " << number << endl;
result[n] = number;
n++;
}
}
}
for (a = 0; a < n; a++) {
cnt = 0;
for (b = (a + 1); b < n; b++) {
if (result[a] == result[b]) {
cnt++;
}
}
if (cnt == 0) {
sum += result[a];
}
}
cout << endl << "Sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital is = " << sum << endl;
return 0;
Comments
Post a Comment