Project Euler task 43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

-------------------------------------------------------------

#include < iostream >

#include < vector >

using namespace std;

vector< unsigned long long int > permutations(vector< unsigned int > _v) {

vector< unsigned long long int > vRes;

unsigned int * piTemp = new unsigned int[_v.size()];

memset(piTemp, 0, sizeof(int) * _v.size());

for (unsigned int k = 0; k < _v.size(); k++)

piTemp[k] = k;

unsigned long long int iDec = 1;

unsigned long long iRes = 0;

for (int k = _v.size() - 1; k >= 0; k--) {

iRes += _v[piTemp[k]] * iDec;

iDec *= 10;

}

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++;

}

}

}

iDec = 1;

iRes = 0;

for (int k = _v.size() - 1; k >= 0; k--) {

iRes += _v[piTemp[k]] * iDec;

iDec *= 10;

}

if (((iRes % 10000000) / 1000000) % 2)

continue;

if (((iRes % 100000000) / 100000) % 3)

continue;

if (((iRes % 10000000) / 10000) % 5)

continue;

if (((iRes % 1000000) / 1000) % 7)

continue;

if (((iRes % 100000) / 100) % 11)

continue;

if (((iRes % 10000) / 10) % 13)

continue;

if ((iRes % 1000) % 17)

continue;

vRes.push_back(iRes);

}

delete piTemp;

return vRes;

}

int main() {

vector< unsigned int > vInput;

vInput.push_back(0);

vInput.push_back(1);

vInput.push_back(2);

vInput.push_back(3);

vInput.push_back(4);

vInput.push_back(5);

vInput.push_back(6);

vInput.push_back(7);

vInput.push_back(8);

vInput.push_back(9);

vector< unsigned long long int > vRes = permutations(vInput);

unsigned long long int iSum = 0;

cout << "size: " << vRes.size() << endl;

for (unsigned int i = 0; i < vRes.size(); i++) {

cout << vRes[i] << endl;

iSum += vRes[i];

}

cout << "Sum: " << iSum << endl;

return 0;

}