Project Euler Problem 32 Solution: Pandigital products

Project Euler Problem 32 Statement

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

Solution

This is a closed–ended recreational problem, so not much thought was given to a clever solution, but here's a table of results I created before trying to solve the problem:

Total Pandigital Digits	Digits Factor 1	Digits Factor 2	Digits Product	Maximum Factor 1	Maximum Factor 2	Solutions	Sum of products
4	1	1	2	3	4	3×4=12	12
5	1	2	2	4	13	4×13=52	52
6	1	2	3	3	54	3×54=162	162
7						None	0
8	1	3	4	6	582	3×582=1746 6×453=2718
8	2	2	4	58	64	24×57=1368 34×52=1768 37×58=2146 58×64=3712	13458
9	1	4	4	4	1963	4×1738=6952 4×1963=7852
9	2	3	4	12	483	12×483=5796¹ 18×297=5346² 27×198=5346² 28×157=4396 39×186=7254 42×138=5796¹ 48×159=7632 (^1,2 Duplicate values are in bold and only one was counted for the sum of products.)	45228

An initial solution

print ([0,0,0,0,12,52,162,0,13458,45228][int(input())])

A brute–force solution

The solution below employs a straightforward brute-force approach used to generate the table above with a runtime of about 30 milliseconds.

Since the product of the factors can never exceed four digits, it is always less than 9876. However, there are no valid factor combinations that would produce a product starting with a 9. Therefore, the upper limit can be safely reduced to 8976. While a small adjustment, this change ensures the solution passes all HackerRank test cases.

The `is_pandigital()` function

The is_pandigital() function takes a string, n, and the intended length of that string, length, as arguments. The string represents a pandigital candidate and is required to pass two tests to qualify as a 1 through length pandigital number:

The length of n must match the specified length.
Each digit from 1 to length must appear exactly once in n.

The function achieves this by truncating the string '1234567890' to the first length characters, creating a reference string containing the digits 1 through length. Then, each character in n is removed from this reference string. If the reference string is empty after all characters are removed, n is confirmed to be a pandigital number.

For example, if n='12648' and length=5, the function truncates '1234567890' to '12345'. Then it removes each character in n ('1', '2', '6', '4', '8') from '12345', leaving '35', which fails the pandigital test. However, a string like '24531' would pass, as it contains only the digits 1 through 5 in some order.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 32

HackerRank Project Euler 32 extends the problem to include all 4–9 digit pandigital sets.

Python Source Code

products = set()
is_pandigital = lambda n, length=9: len(n)==length and not '1234567890'[:length].strip(n)
N = int(input())
for i in range(2, 99):
    j = i+1
    while i*j < 8976:
        if is_pandigital(f"{i}{j}{i*j}", N): products.add(i*j)
        j+= 1
print (sum(products))

Last Word

A Python set() was used to collect unique products and eliminate duplicates.
f"{i}{j}{i*j}" concatenates the separate values together.