2
\$\begingroup\$

I'm working on this kata from Codewars. The task is:

Given a certain number, how many multiples of three could you obtain with its digits?

Supose that you have the number 362. The numbers that can be generated from it are:

362 → 3, 6, 2, 36, 63, 62, 26, 32, 23, 236, 263, 326, 362, 623, 632

I've written the following recursive function to calculate all possiblities:

const findMult_3 = (num) => {

  const powerset = (set) => {
    const combinations = []
    const combine = (prefix, chars) => {
      for (let i = 0; i < chars.length; i++) {
        const newPrefix = parseInt(prefix + chars[i])
        if (!combinations.includes(newPrefix)) {
          combinations.push(newPrefix)
        } else {
          console.log('encountered duplicate')
        }
        combine(newPrefix, chars.filter((x, ind) => ind !== i))
      }
    }
    combine('', set)
    return combinations.sort((a, b) => a - b)
  }

  const allCombinations = powerset(num.toString().split(''))
  const factorsOfThree = allCombinations.filter(x => x % 3 === 0).filter(x => x !== 0)

  return [factorsOfThree.length, factorsOfThree.pop()]

}

findMult_3(43522283000229)

I noticed early on that I encountered a lot of duplicate cases, hence the console.log('encountered duplicate') flag.

Execution of this algorithm is taking an extremely long time for large numbers, eg 43522283000229.

How can I improve the performance of this code? Or should it be scrapped entirely?

\$\endgroup\$
  • 1
    \$\begingroup\$ @ischnmn This isn't Stack Overflow. Can you please clarify whether the code produces the correct output in the format as required by the challenge or not? \$\endgroup\$ – Mast Aug 7 '18 at 11:05
  • 2
    \$\begingroup\$ @Mast Yes, the code produces correct output. It only fails because it surpasses a 12 second timeout limit when executing huge numbers. \$\endgroup\$ – j_d Aug 7 '18 at 11:07
3
\$\begingroup\$

How can I improve the performance of this code? Or should it be scrapped entirely?

I personally would consider taking a wildly different approach, but there are major performance improvements which can be made and which might be sufficient for your purposes.

        if (!combinations.includes(newPrefix)) {
          combinations.push(newPrefix)
        }

combinations is an array: combinations.includes is a linear search. I understand from the question that you're using Node, so the best way to improve this is probably hashset. However, if you want to stick to JavaScript primitives you can achieve a similar (albeit hacky) performance improvement by using an object as a hashmap:

        if (!combinations.hasOwnProperty(newPrefix)) {
          combinations[newPrefix] = 1;
        }

         else {
          console.log('encountered duplicate')
        }

If you also use a map for the remaining digits, you can ensure that you only try to extend with each digit once, and avoid the unnecessary work of handling duplicates.


I said that I would consider a wildly different approach. In combinatorics, if you only want to count objects then ideally you don't generate them all. You may have been taught in primary school that you can check whether a number is a multiple of 3 by adding its digits and seeing whether you get a multiple of 3. What's really going on there is that \$10 \equiv 1 \pmod{3}\$, so \$10^n \equiv 1 \pmod{3}\$ for any non-negative integer \$n\$. Thus you can cluster numbers by their values modulo 3. There are various directions in which this can be taken, and the need to avoid duplicates complicates things, so I suggest that you first try the earlier suggestions.

\$\endgroup\$
3
\$\begingroup\$

Unfortunately I would reconsider the algorithm a bit further.

A multiple of 3 is characterized by a useful rule:

A number is divisible by 3 if the sum of its digits is divisible by 3.

This means that for {2, 3, 6}, {2, 6}, {2, 3} any combination will fail.

So bags (unordered list of possible repeated elements) is the way to go: loop over all bags.

The maximum value is given by the bag with most elements, the digits in decreasing order.

For a set of size n the number of combinations are 2n, if not considering 0. For a bag this is different: 6a06b3 = 6b06a3. Given different digits di with frequency fi the total number of combinations is (Σi fi)! / Πj(fj!)

  • case of 0
  • number of occurences of some digit

I leave the joy of a formula to you.

The example data to check:

3, 6, 2, 36, 63, 62, 26, 32, 23, 236, 263, 326, 362, 623, 632
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.