Project Euler Problem 38 Solution: Pandigital multiples

Project Euler Problem 38 Statement

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?

Solution

With all the deliberation and justification determining a search range I tried a simple brute force solution to see what I was getting into. But, in 3ms the answer sprinted across the screen and that was that.

HackerRank proposed a more extended version that required some thought. But, after submitting a modified brute–force solution it was easily accepted with a run time of 30ms.

Strangely, they set the search limit to 100,000 when it's obvious that only 9,999 will suffice—anything bigger is superfluous. With the search limit capped at 9,999 this solution simply loops through all values of n and each multiplier of 2 through 5, concatenating products and checking for pandigitality. The worst case scenario is 40,000 iterations and the benefit is not having to justify any search parameters.

Also, since this is a close-ended problem, no real concern for optimization is required. Once all the numbers are found that make 1—8 and 1—9 concatenated pandigital numbers the universe of possibilities is complete.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 38

HackerRank Project Euler 38 includes either 1—9 or 1—8 pandigital numbers and has you find the multipliers 100 ≤ N ≤ 10⁵ in ascending order.

Python Source Code

def is_pandigital(n, s=9): return len(n)==s and not '1234567890'[:s].strip(n)
i,k = map(int, input().split())
for n in range(1, min(10000,i)):
    p = str(n)
    for j in range(2,6):
        p+= str(n*j)
        if is_pandigital(p, k): print (n)

Last Word

Here is a listing of the solution universe I mentioned earlier generated by the program listed above. The symbol || is the concatenation operator.

All 1—8 Pandigital solutions
  18 × 1 ||  18 × 2 || 18 × 3 || 18 × 4 = 18365472
  78 × 1 ||  78 × 2 ||  78 × 3 = 78156234
1728 × 1 || 1728 × 2 = 17283456
1764 × 1 || 1764 × 2 = 17643528
1782 × 1 || 1782 × 2 = 17823564
1827 × 1 || 1827 × 2 = 18273654
2178 × 1 || 2178 × 2 = 21784356
2358 × 1 || 2358 × 2 = 23584716
2718 × 1 || 2718 × 2 = 27185436
2817 × 1 || 2817 × 2 = 28175634
3564 × 1 || 3564 × 2 = 35647128
3582 × 1 || 3582 × 2 = 35827164
4176 × 1 || 4176 × 2 = 41768352
4356 × 1 || 4356 × 2 = 43568712

All 1—9 Pandigital solutions
   9 × 1 ||    9 × 2 ||   9 × 3 || 9 × 4 || 9 × 5 = 918273645
 192 × 1 ||  192 × 2 || 192 × 3 = 192384576
 219 × 1 ||  219 × 2 || 219 × 3 = 219438657
 273 × 1 ||  273 × 2 || 273 × 3 = 273546819
 327 × 1 ||  327 × 2 || 327 × 3 = 327654981
6729 × 1 || 6729 × 2 = 672913458
6792 × 1 || 6792 × 2 = 679213584
6927 × 1 || 6927 × 2 = 692713854
7269 × 1 || 7269 × 2 = 726914538
7293 × 1 || 7293 × 2 = 729314586
7329 × 1 || 7329 × 2 = 732914658
7692 × 1 || 7692 × 2 = 769215384
7923 × 1 || 7923 × 2 = 792315846
7932 × 1 || 7932 × 2 = 793215864
9267 × 1 || 9267 × 2 = 926718534
9273 × 1 || 9273 × 2 = 927318546
9327 × 1 || 9327 × 2 = 932718654

if n > 1 as the problem states, then there are no solutions for k ∈ {2,3,4,5,6,7}, where k is the 1—k pandigital number.