Project Euler #43: Why does my answer take so long?

Question

I am working on Problem 43

I have done a brute force solution. But it should execute in O(n) time.

On my computer it takes a few hours to complete. Is there anything I can do to speed up the computational complexity?


const main = () => {
    let total = 0;
    for (let i = 1023456789; i < 9876543211; i++) {
    // for (let i = 1406357289; i < 1406357290; i++) {
        if (isPandigital(i)) {
            var d = i.toString().split("");
            if (checkSubString (d[1], d[2], d[3], 2) &&
                checkSubString (d[2], d[3], d[4], 3) &&
                checkSubString (d[3], d[4], d[5], 5) &&
                checkSubString (d[4], d[5], d[6], 7) &&
                checkSubString (d[5], d[6], d[7], 11) &&
                checkSubString (d[6], d[7], d[8], 13) &&
                checkSubString (d[7], d[8], d[9], 17)) {
                total += i;
            }
        }
    }
    return total;
};

const checkSubString = (d1, d2, d3, prime) => parseInt(`${d1}${d2}${d3}`) % prime === 0;

const isPandigital = num => {
    var allNums = num.toString().split("").map(item => parseInt(item, 10)).sort();
    for (var k = 0; k < allNums.length; k++) {
        if (allNums[k] !== k) {
            return false;
        }
    }
    return true;
}

console.log(main()); // 16695334890

How about creating a table of powers of 10, then extracting triples of digits by using the modulo operator with appropriately chosen powers of 10? EDIT: Sort of similarly, in isPandigital, you can loop over the digits by using the modulo and divison operators (mind to floor after the division); I'd suggest storing which digits you've already found in an array, returning false when there is a duplicate digit (if there isn't, and it's of the right length, it's pandigital). — tomsmeding, Mar 04 '20 at 04:38

score 3 · Accepted Answer · answered Mar 04 '20 at 04:43

Rather than iterating over all numbers inside the range, how about instead generating only the permutations which result in pandigital numbers, and then iterating over them instead? That'll cut down on a lot of the calculations:

Tweaking the permuting function from this answer:

const checkSubString = (d1, d2, d3, prime) => `${d1}${d2}${d3}` % prime === 0;
const main = () => {
  let total = 0;
  const pandigitalNumbers = permut('1234567890').filter(char => char[0] !== '0');
  for (const i of pandigitalNumbers) {
    var d = [...String(i)];
    if (checkSubString(d[1], d[2], d[3], 2) &&
      checkSubString(d[2], d[3], d[4], 3) &&
      checkSubString(d[3], d[4], d[5], 5) &&
      checkSubString(d[4], d[5], d[6], 7) &&
      checkSubString(d[5], d[6], d[7], 11) &&
      checkSubString(d[6], d[7], d[8], 13) &&
      checkSubString(d[7], d[8], d[9], 17)) {
      total += Number(i);
    }
  }
  return total;
};
console.log(main());


function permut(string) {
  const arr = [];
  if (string.length < 2) return string;
  for (let i = 0; i < string.length; i++) {
    const char = string[i];
    if (!string.includes(char)) continue;
    const remainingString = string.slice(0, i) + string.slice(i + 1, string.length);
    for (var subPermutation of permut(remainingString))
      arr.push(char + subPermutation)
  }
  return arr;
}

The snippet above runs in about 4 seconds on my machine.

Ooohh yeah, that makes a lot of sense. I didn't even think of that. Thanks a lot!! — Jerome, Mar 04 '20 at 04:47
Two tweaks: d4 has to be even and d6 can only be 0 or 5. That means you can terminate some selections early. — rossum, Mar 04 '20 at 15:47

Project Euler #43: Why does my answer take so long?

1 Answers1