Project Euler task 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 
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 >
#include < vector >
using namespace std;
vector< int > findPandigitalProducts(vector< int > _v) {
vector< int > vRes;
int * piTemp = new int[_v.size()];
memset(piTemp, 0, sizeof(int) * _v.size());
for (int k = 0; k < _v.size(); k++)
piTemp[k] = k;
while (1) {
int j;
// j
// |
// 0 1 2 3 4 5 6
// Find element, whose value is less than
// the value of the next element (5 < 6).
for (j = _v.size() - 1; j >= 1; j--)
if (piTemp[j] > piTemp[j - 1]) {
j--;
break;
}
// Nothing to process.
if (j < 0)
break;
// find the minimal element that is greater than piTemp[j]
int i = _v.size() - 1;
int iTempValue = -1;
for (int k = _v.size() - 1; k > j; k--)
if (piTemp[k] > piTemp[j] && (iTempValue < 0 || iTempValue > piTemp[k])) {
iTempValue = piTemp[k];
i = k;
}
if (iTempValue == -1)
break;
iTempValue = 0;
// swap (i, j)
int iTemp = piTemp[i];
piTemp[i] = piTemp[j];
piTemp[j] = iTemp;
int iSwaps = 1;
while (iSwaps) {
iSwaps = 0;
for (int k = _v.size() - 2; k > j; k--) {
if (piTemp[k] > piTemp[k + 1]) {
int iTmp = piTemp[k + 1];
piTemp[k + 1] = piTemp[k];
piTemp[k] = iTmp;
iSwaps++;
}
}
}
// calculate the first number
int iA = _v[piTemp[0]];
// calculate the second number
int iB = 0;
for (int i = 1; i < 5; i++) {
iB *= 10;
iB += _v[piTemp[i]];
}
// calculate the result
int iC = 0;
for (int i = 5; i < 9; i++) {
iC *= 10;
iC += _v[piTemp[i]];
}
if (iA * iB == iC) {
bool bFlag = 0;
for (int i = 0; i < vRes.size(); i++)
if (vRes[i] == iC) {
bFlag = 1;
break;
}
if (!bFlag)
vRes.push_back(iC);
}
// calculate the first number
iA = 0;
for (int i = 0; i < 2; i++) {
iA *= 10;
iA += _v[piTemp[i]];
}
// calculate the second number
iB = 0;
for (int i = 2; i < 5; i++) {
iB *= 10;
iB += _v[piTemp[i]];
}
// product
iC = 0;
for (int i = 5; i < 9; i++) {
iC *= 10;
iC += _v[piTemp[i]];
}
if (iA * iB == iC) {
bool bFlag = 0;
for (int i = 0; i < vRes.size(); i++)
if (vRes[i] == iC) {
bFlag = 1;
break;
}
if (!bFlag)
vRes.push_back(iC);
}
}
delete piTemp;
return vRes;
}
int main() {
vector< int > vNums;
vNums.push_back(1);
vNums.push_back(2);
vNums.push_back(3);
vNums.push_back(4);
vNums.push_back(5);
vNums.push_back(6);
vNums.push_back(7);
vNums.push_back(8);
vNums.push_back(9);
vector< int > vRes = findPandigitalProducts(vNums);
int iSum = 0;
for (int i = 0; i < vRes.size(); i++)
iSum += vRes[i];
cout << iSum << endl;
return 0;
}
Comments