Project Euler/32

Problem Statement

An n-digit number is pandigital if it makes use of all digits 1 to n exactly once

Example: the 5-digit number 15234 is pandigital for digits 1 thru 5

The product 7254 is pandigital, for digits 1 thru 9:

$ 39 \times 186 = 7254 $

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

Note that some products can be obtained in more than one way, so only include it once in the sum

Approach

Set Bounds

Set the bounds for the product:

C = 10^6 (maximum 5-digit number)

Set the bounds for the multiplicand and multiplier:

A x B = C

In theory, search space will be all numbers up to 4 digits. In reality, can deduce the range of one number based on what we choose as the other number

For example:

If A is a 1-digit number, B ranges up to 10^5 (maximum 4-digit number)

If A is a 2-digit number, B ranges up to 10^4 (maximum 3-digit number)

etc...

Iterate and Factor

Iterate over each possible product

For each possible product,

Generate a list of factors

Generate all possible ways to partition factors into 2 groups

Compute product of each group

Add product to set of pandigital products

End for

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem032.java