[C/C++] Project Euler #32 - Pandigital Products

Project Euler #32 is a relatively low-difficulty problem with a difficulty level of 5%.

A pandigital number is a number formed by using all digits within a specific range exactly once. For example, combinations such as 123456789 or 391867254, which include all digits from 1 to 9 exactly once, are called pandigital. In this problem, the condition requires using all digits from 1 to 9 exactly once.

The goal of the problem is to find all valid equations of the form \(a \times b = c\) such that, when a, b, and c are concatenated, the resulting number includes all digits from 1 to 9 exactly once.  For example, \(39 \times 186 = 7254\) results in 391867254, which is a pandigital number because it uses each digit from 1 to 9 exactly once.

The task is to find all such combinations that satisfy the condition, collect the values of c, eliminate duplicates, and calculate their sum. For instance, if the possible values of c are 7254 and 7632, their sum would be 14886, which is the final answer.

---

For this problem, I considered the following approach:

Instead of generating two numbers first and then checking their product, it may be more efficient to start with a number n and find its factors. By factoring n, we can obtain two numbers, which can then be checked to see if they satisfy the pandigital condition.

To check whether a number is pandigital, I used a simple logic that relies on a bitmask. The core idea is that if there are duplicate digits in the concatenated string or if all required digits are not accounted for, then the number is not pandigital. If all digits are present without any duplicates, then the number is perfectly pandigital.

 

pan digital

Here is a basic outline of the pandigital checking logic:

//------------------------------------------------
//    Project Euler #32 - Pandigital Products
//        - by Aubrey Choi
//        - created at 2015-02-04
//------------------------------------------------
#include <stdio.h>

bool IsPanDigital(int n);

inline bool Check(int &k, int q)
{
    while( q )
    {
        int c = q%10;
        if( c == 0 || (k & (1<<c)) ) return false;
        k |= 1<<c;
        q /= 10;
    }
    return true;
}

int main()
{
    int sum = 0;

    for( int i = 1234 ; i <= 98765 ; i++ )
        if( IsPanDigital(i) ) sum += i;
    printf("Ans = %d\n", sum);
}

bool IsPanDigital(int n)
{
    int k = 0;

    if( Check(k, n) == false ) return false;

    for( int i = 2 ; i*i < n ; i++ )
    {
        if( n%i ) continue;
        int u = k;
        if( Check(k, n/i) && Check(k, i) && k == 0x3fe )
        {
            printf("%dx%d=%d\n", i, n/i, n);
            return true;
        }
        k = u;
    }
    return false;
}