Problem Analysis
We are asked to find every multiplication identity a * b = c whose three numbers, written side by side, use each digit from 1 to 9 exactly once - a property called being pandigital - and then to sum the distinct products. A naive search over wide ranges of a and b would waste enormous effort, so the first thing I did was reason about digit counts to shrink the search space before writing any enumeration code.
The pivotal observation is a digit-count identity. The concatenation of a, b, and c must be exactly 9 characters long, so the digit-lengths of the three numbers sum to 9. Multiplication, in turn, almost preserves additivity of length: the product of an m-digit number and an n-digit number has either m+n-1 or m+n digits. This follows directly from logarithms, since the digit-count of x is roughly log10(x) + 1 and logarithms turn products into sums. Combining "lengths sum to 9" with "product length is about the sum of operand lengths" leaves only two consistent shapes for (len(a), len(b), len(c)): (1, 4, 4) and (2, 3, 4). Every other arrangement - a 3x3 product, a 1x3 product, and so on - fails this arithmetic and can be discarded without ever computing a product. This combinatorial pruning step is the heart of the solution.
With the two splits fixed, I enumerate ordered selections of digits for a and then for b from the digits a did not use, compute c = a * b, and verify pandigitality. The number of candidates is a small fixed constant (on the order of a couple of thousand), so the runtime is O(1) - it does not grow with any input, because the input is fixed at the digits 1 through 9.
Solution Approach
Constrained Permutation Enumeration with Digit-Split Filtering (Python and C)
Both the Python and C solutions implement the same algorithm; they differ only in how they generate the permutations. The steps are:
- Fix the two valid splits
(a_len, b_len)as(1, 4)and(2, 3). In each, the product has 4 digits, giving1+4+4=9or2+3+4=9. - For each split, generate every ordered selection of
a_lendigits from {1,...,9} to forma, then every ordered selection ofb_lendigits from the unused digits to formb. - Compute
c = a * band check that the concatenation of all three is 1-through-9 pandigital. Becauseaandbalready draw distinct digits from the pool, this check effectively verifies thatcsupplies exactly the remaining digits. - Insert each valid product into a set so a product reachable through more than one
(a, b)pair is counted only once, then sum the set.
The Python version expresses the whole search as a single set comprehension. It loops over the two splits, uses itertools.permutations(nine_digits, a_len) for a, and feeds a generator (d for d in nine_digits if d not in a) into a second itertools.permutations(..., b_len) call so that b draws only from unused digits. The walrus operator (:=) assigns a_str, b_str, and c inside the filter condition so they are computed once and reused. Wrapping the generator in set() deduplicates, and sum() finishes the job. The helper is_nine_pandigital confirms both that the decimal string is 9 characters long and that its character set equals {1,...,9}.
The C version reproduces the same logic with explicit nested loops, since there is no permutation library to lean on. For the (1, 4) split it builds a rem[] array of the eight digits not used by a, then runs four nested loops with collision guards (if (q1 == q0) continue) to enumerate the ordered 4-selections. The (2, 3) split uses two outer loops for a and three inner loops for b. The pandigital test formats the three integers into a buffer with snprintf, rejects immediately if the combined length is not 9, then marks each digit in a seen[10] array, rejecting any repeat or any zero. Uniqueness is enforced by set_add, which linearly scans the small products[] array before inserting.