**This is our solution and implementation to problem #43 on Project Euler.**

Our code is written in TypeScript, a language which is built on-top of JavaScript and transpiles to it. We've included the problem statement, our code (which is commented for greater clarity), our video which outlines our analysis and implementation approach, and the solution + how long it took to calculate it.

**Note:** the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.

If you would like to view the original problem and solve it, please visit: Sub-String Divisibility on Project Euler. If you're having trouble solving this problem, or are just curious to see how others have solved it, feel free to take a look, but please put solid effort into solving this before viewing the actual solution to the problem.

### Problem Statement

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*_{1} be the 1^{st} digit, *d*_{2} be the 2^{nd} digit, and so on. In this way, we note the following:

*d*_{2}*d*_{3}*d*_{4}=406 is divisible by 2*d*_{3}*d*_{4}*d*_{5}=063 is divisible by 3*d*_{4}*d*_{5}*d*_{6}=635 is divisible by 5*d*_{5}*d*_{6}*d*_{7}=357 is divisible by 7*d*_{6}*d*_{7}*d*_{8}=572 is divisible by 11*d*_{7}*d*_{8}*d*_{9}=728 is divisible by 13*d*_{8}*d*_{9}*d*_{10}=289 is divisible by 17

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

### Our Solution

Our solution is given in the TypeScript code below:

` ````
import { AbstractSolution, RunSolution } from "../../utils/solution";
@RunSolution
export class Solution43 extends AbstractSolution {
//divisibility map, based on the list given in the problem
private divisibilityMap = [
-1,
2,
3,
5,
7,
11,
13,
17
];
getProblemName(): string {
return "Sub-String Divisibility";
}
protected solve() {
return this.doSolve();
//return this.isQualified("1406357289");
}
private doSolve(): number {
let sum = 0;
//in our video we used the Combinations class, but instead we'll generate ourselves to save some time
/*Combinations.forEachNPermutations(10, [0,1,2,3,4,5,6,7,8,9], (perm: string) => {
sum += (this.isQualified(perm) ? parseInt(perm) : 0);
});*/
//define the first number of each perm, then call recursive "forEachPerm" to get the rest
//this way, we can avoid having invalid "0" perms
for (let i=1; i<10; i++) {
const choices = new Array(9).fill(0).map((_, ind) => {
if (ind + 1 === i) {
return 0;
}
return ind+1;
});
this.forEachPerm(10, choices, (perm: string) => {
sum += (this.isQualified(perm) ? parseInt(perm) : 0);
}, "" + i);
}
return sum;
}
/**
* Recursively generate permutations given a set of choices
* Invoke a callback once we have the full string
* @param lenTotal
* @param choices
* @param callback
* @param permSoFar
*/
private forEachPerm(lenTotal: number, choices: number[], callback: (perm: string) => void, permSoFar = ""): void {
//recursive case
if (choices.length === 1) {
callback(permSoFar + choices[0]);
} else {
choices.forEach((choice, ind) => {
const remainingChoices = [...choices];
remainingChoices.splice(ind, 1);
this.forEachPerm(lenTotal, remainingChoices, callback, permSoFar + "" + choice)
});
}
}
/**
* This assumes perm is 10 digit permutation of 0-9 digits
* @param perm
*/
private isQualified(perm: string): boolean {
//7: as length is assumed to be 10
for (let i=1; i<8; i++) {
const subPerm = perm.substring(i, i+3);
const subPermInt = parseInt(subPerm);
//console.log({subPerm, div: this.divisibilityMap[i]})
if (subPermInt % this.divisibilityMap[i] !== 0) {
return false;
}
}
console.log("====>", perm);
return true;
}
}
```

### Results

This implementation found the solution in **1237ms**.

If you would like to view the answer, click below to reveal. Please consider reviewing the implementation and trying to code your own solution before viewing the answer.

## View Answer

The answer is

**16695334890.**

All of our solutions are hosted on GitHub. The code on this page was pulled from the repo and the solution and execution time were calculated based on that code.