[C/C++] Project Euler #38 - Pandigital Multiples

In Project Euler Problem 38, the goal is to use the concepts of “pandigital numbers” and “multiplication” to find the largest number that satisfies specific conditions. A pandigital number is defined as a number in which each digit from 1 to 9 appears exactly once. For example, 192384576 is considered a pandigital number because it contains all digits from 1 to 9 without repetition.

 

The problem requires selecting an integer n and another integer k , then multiplying n by 1, 2, 3, …, k , and concatenating the results to form a single number. The task is to check whether this concatenated number is a pandigital number. Additionally, the objective is to find the largest possible pandigital number that can be created through this process.

 

For instance, when n = 192 and k = 3 , the calculations are \(192 \times 1 = 192 \), \(192 \times 2 = 384 \), and \(192 \times 3 = 576 \). Concatenating these results gives 192384576, which is a pandigital number and meets the conditions of the problem.

 

The key challenge of the problem is to identify the largest pandigital number among all such combinations. This involves exploring the range of n and k effectively to design an algorithm that determines the optimal result. The ultimate goal is to compute the largest number that includes all digits from 1 to 9 exactly once.

---

This problem is rated as having a difficulty level of 5%.

Since the objective is to find the maximum value, the solution can focus on starting from 4-digit numbers and sequentially testing whether their concatenated results with their multiples (up to k = 2 ) form a pandigital number.

 

numbers

 

Below is the source code I have written.

//------------------------------------------------
//    Project Euler #38 - Pandigital Multiples
//        - by Aubrey Choi
//        - created at 2015-03-20
//------------------------------------------------
#include <stdio.h>

bool IsPandigitalMultiply(int n);

int main()
{
    int ans;
    for( ans = 9876 ; !IsPandigitalMultiply(ans) ; ans-- );
    printf("Ans = %d%d\n", ans, ans*2);
}

bool IsPandigitalMultiply(int n)
{
    unsigned short s = 0;
    for( int i = 1 ; ; i++ )
    {
        int t = n*i;
        while( t )
        {
            int p = t%10;
            if( p == 0 ) return false;
            t /= 10;
            if( s & (1<<p) ) return false;
            s |= 1<<p;
        }
        if( s == 0x3fe ) return true;
    }
    return false;
}

To check whether a number is pandigital, I used a variable called s, which acts as a bit flag. If duplicate digits occur, the number obviously cannot be pandigital. When all bits are set, the result will be the number 0x3fe. Therefore, if the processed result equals 0x3fe, the function returns true.

 

In fact, if the original number itself contains duplicate digits, it cannot be pandigital. Thus, using numbers without duplicate digits (typically numbers generated as permutations) can reduce the testing time further. However, in this case, I implemented it in a simple way for demonstration purposes.