Problem 43 is the 51st Project Euler problem I've solved. To do it, I've used a couple of tricks that reduced the runtime considerably from a full brute-force. A full brute-force for such a problem would be going over all 10-digit numbers, detecting pandigital ones and checking the requested property. Since there are 10 billion 10-digit numbers, this would take a long time. Here are some ideas of how to reduce the run-time: First of all, there are only 3,628,800 (10!) 0 to 9 pandigital numbers, so there's no need to examine all 10 billion 10-digit numbers. Second, the special property we're looking for in the numbers can help us considerably reduce the amount of candidates to test. What I did is consider only numbers whose last 3 digits divide by 17. There are only 58 such numbers (1 to 58, as 17 * 59 > 1000). For each, we should only check the permutations of the 7 remaining digits. Since there are 5040 permutations of 7 digits, we have to check only 58 * 5040 = 292320 candidates for the property. This, of course, can be reduced further by considering the division by 13 as well, and so on, so I'm sure the problem can even be solved using a pen, some paper and a calculator in not too much time.

Comments

comments powered by Disqus