Problem 170: Find the Largest 0 to 9 Pandigital That Can Be Formed by Concatenating Products

Project Euler Problem 170 Solution

EulerSolve provides an optimized solution for Project Euler Problem 170, Find the Largest 0 to 9 Pandigital That Can Be Formed by Concatenating Products, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We seek the largest 10-digit number $P$ that uses the digits $0,1,\dots,9$ exactly once and can be written as a concatenation of decimal products $$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$ for some positive integer multiplier $m$ and positive integers $x_1,\dots,x_t$. The input-side concatenation $$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$ must also be 0-to-9 pandigital. All numbers are interpreted in ordinary decimal notation, so a multi-digit block may not begin with 0. Mathematical Approach The crucial simplification is to search from the output side. Instead of guessing $m$ and the multiplicands first, the implementation scans possible 10-digit pandigital outputs in descending order and asks whether each one can be decomposed into valid product blocks. From a two-sided identity to a one-sided search Take a candidate output string $Y$. If $Y$ is valid, then some choice of block boundaries turns it into decimal integers $$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$$ where each block satisfies $$p_i=m x_i.$$ So the entire problem becomes: choose a 10-digit pandigital output $Y$, choose block boundaries, and check whether there exists a common multiplier $m$ making the reconstructed input $m\Vert x_1\Vert\cdots\Vert x_t$ pandigital as well. Choosing the product blocks A 10-digit string has 9 gaps between consecutive digits....

Detailed mathematical approach

Problem Summary

Take an integer $n$, the multiplier, and $k\ge2$ further integers $a_1,\dots,a_k$, written in decimal without leading zeros. Writing the products $na_1,\dots,na_k$ one after another gives the concatenated product of $n$ and $(a_1,\dots,a_k)$, and writing $n,a_1,\dots,a_k$ one after another gives the concatenated input. In the statement's example, $6\times1273=7638$ and $6\times9854=59124$ give the concatenated product $763859124$ and the concatenated input $612739854$, both using every digit from $1$ to $9$ exactly once. We must find the largest concatenated product that is a 0 to 9 pandigital $10$-digit number, using each of the digits $0$ to $9$ exactly once, and whose concatenated input is also a 0 to 9 pandigital $10$-digit number. ^[1] ^[2]

The whole solution in one sentence: we go through the ten-digit numbers that use every digit once from the largest downwards, try every way of cutting each one into products and every common divisor of those products as the multiplier, and stop at the first number for which the multiplier followed by the quotients again uses every digit once.

Mathematical Approach

We write $x\Vert y$ for the decimal concatenation of $x$ and $y$, so that $6\Vert1273\Vert9854=612739854$, $d(x)$ for the number of decimal digits of $x$, and $n\times(a_1,\dots,a_k)$ for a representation, a choice of multiplier and factors. Sections 1 to 5 prove the published search exact, Sections 6 to 8 derive two properties that explain which multipliers occur, and Section 9 treats a factor $0$.

1. Running the example backwards

Suppose we only know $Y=763859124$. To recover a multiplier and its factors, we must choose where to cut $Y$ into products and which multiplier to divide them by. Cutting after the fourth digit gives the blocks $7638$ and $59124$. A multiplier must divide both blocks and therefore also their greatest common divisor (gcd), the largest integer dividing both, since every common divisor divides the gcd. ^[5] Here $\gcd(7638,59124)=6$, which leaves the divisors $6$, $3$, $2$ and $1$. The divisor $m=6$ gives $6\Vert1273\Vert9854=612739854$, which uses every digit from $1$ to $9$ once, while $m=3$, $2$ and $1$ give the ten-digit strings $3\Vert2546\Vert19708$, $2\Vert3819\Vert29562$ and $1\Vert7638\Vert59124$. Trying all $2^8-1=255$ ways to cut the nine digits finds two further representations, $3\times(2546197,8)$ and $3\times(2546,197,8)$, both with the concatenated input $325461978$. A number can therefore have several representations with different multipliers, and a search must try every cut.

2. Admissible cuts

A candidate $Y$ has nine gaps between neighbouring digits; a cut is a nonempty set of gaps, since at least two products are required, so there are $2^9-1=511$ cuts. Products are written without leading zeros, so a block of two or more digits may not begin with $0$; only the single digit $0$ may, as the product of $n$ and a factor $0$ (Section 9). The first digit of $Y$ is not $0$. If its $0$ is not the last digit either, the $2^7=128$ cuts that cut just before the $0$ but not just after it are forbidden, leaving $383$ admissible cuts; if $0$ is the last digit, all $511$ are admissible. Without the factor $0$, all $2^8=256$ cuts that use the gap just before the $0$ are forbidden, leaving $255$ cuts for every candidate.

3. The multiplier divides the gcd

Fix an admissible cut of $Y$ into blocks $p_1,\dots,p_k$ and let $g=\gcd(p_1,\dots,p_k)$. For a positive divisor $m$ of $g$ put $q_i=p_i/m$ and define the digit string

$$I_m=m\Vert q_1\Vert q_2\Vert\cdots\Vert q_k.$$

Claim. $Y$ is a valid concatenated product if and only if, for some admissible cut and some divisor $m$ of its $g$, the string $I_m$ is a 0 to 9 pandigital $10$-digit number.

Proof. Suppose $Y=na_1\Vert\cdots\Vert na_k$ with a pandigital concatenated input. The products $na_i$ are the blocks of an admissible cut, and $n$ divides each of them, hence divides $g$, ^[5] and $I_n=n\Vert a_1\Vert\cdots\Vert a_k$ is the concatenated input. Conversely, if $m\mid g$, then $m$ divides every block, the quotients $q_i$ are integers with $mq_i=p_i$, and $I_m$ is their concatenated input. $\square$

A block $0$ does not change the gcd, since $\gcd(x,0)=x$. The divisor $1$ never succeeds, because $I_1=1\Vert Y$ has eleven digits, so a cut with $g=1$ cannot work, although the programs still try it.

4. Worked example: the smallest valid number

Take $Y=1204739586$. Its $0$ is the third digit, so it has $383$ admissible cuts, and $372$ of them have $g=1$. The cut $120\,|\,4739586$ has $g=\gcd(120,4739586)=6$, and its four divisors give

$m=6$: $6\Vert20\Vert789931=620789931$, only nine digits;
$m=3$: $3\Vert40\Vert1579862=3401579862$, pandigital;
$m=2$: $2\Vert60\Vert2369793=2602369793$, in which $2$, $3$, $6$ and $9$ appear twice;
$m=1$: eleven digits.

So $3\times40=120$ and $3\times1579862=4739586$ prove that $Y$ is valid. Altogether $Y$ has five representations, all with multiplier $3$ and the same concatenated input $3401579862$: besides $3\times(40,1579862)$ they are $3\times(40157986,2)$, $3\times(40,157986,2)$ and two that use a factor $0$ (Section 9). No smaller number is valid, as the verification below shows.

5. Why the first hit is the largest

All candidates have ten digits, so the larger of two is the one whose digit string comes later in dictionary order, decided at the first position where they differ. The programs test them in this order from $9876543210$ downwards: C++ and Java repeatedly step to the previous arrangement, ^[6] and Python sorts the list of all arrangements in decreasing order. Skipping those that begin with $0$ leaves $9\cdot9!=3\,265\,920$ of the $10!=3\,628\,800$ arrangements. ^[3] As the test of Section 3 accepts exactly the valid numbers, every candidate before the first accepted one is invalid, and the first accepted candidate is the largest valid number.

6. The multiplier is a multiple of 3

Let $S(x)$ be the digit sum of $x$. Since $10\equiv1\pmod 9$, every power of ten is congruent to $1$, and hence $x\equiv S(x)\pmod 9$; this is the rule behind casting out nines. ^[4] The digit sum of a concatenation is the sum of the digit sums of its pieces, and the digits $0$ to $9$ add up to $45$. ^[2] With $A=a_1+\dots+a_k$, the concatenated input and the concatenated product therefore give

$$\begin{aligned}n+A&\equiv S(n)+\sum_i S(a_i)=45\equiv0\pmod 9,\\ nA&=\sum_i na_i\equiv\sum_i S(na_i)=45\equiv0\pmod 9.\end{aligned}$$

The first line gives $A\equiv-n$, and then the second gives $-n^2\equiv0\pmod 9$. So $9\mid n^2$, and since $3$ is prime this forces $3\mid n$. The digits $1$ to $9$ also add up to $45$, so the argument covers the example of the statement as well: $6+11127=11133=9\cdot1237$ and $6\cdot11127=66762=9\cdot7418$.

7. With positive factors, the multiplier has at most two digits

For positive $x$ and $y$, the bounds $10^{d(x)-1}\le x\lt10^{d(x)}$ and the same bounds for $y$ give

$$\begin{aligned}10^{d(x)+d(y)-2}&\le xy\lt10^{d(x)+d(y)},\\ d(xy)&=d(x)+d(y)-1+c,\qquad c\in\{0,1\}.\end{aligned}$$

Let $c_i$ be this $c$ for the product $na_i$. Substituting the formula for $d(na_i)$ into the digit count $\sum_i d(na_i)=10$ of the product and using the count $d(n)+\sum_i d(a_i)=10$ of the input gives

$$\sum_{i=1}^{k}c_i=1-(k-1)\bigl(d(n)-1\bigr).$$

The left side is at least $0$, while for $k\ge2$ and $d(n)\ge3$ the right side is at most $-1$, so only two cases remain:

$d(n)=1$: exactly one product has one digit more than its factor, and every other product has as many digits as its factor;
$d(n)=2$: then $k=2$, and both products have exactly one digit more than their factors.

The total number of digits cancels, so the count also covers the nine-digit example of the statement, where $1273\to7638$ keeps four digits and $9854\to59124$ gains one. A two-digit example is $12\times(30,489576)$${}=(360,5874912)$, which gives the valid number $3605874912$ with the concatenated input $1230489576$.

8. Which multipliers remain

For positive factors, Sections 6 and 7 leave the multipliers $3$, $6$, $9$ and the two-digit multiples of $3$. The digits of $n$ belong to the concatenated input and must be different, which removes $33$, $66$ and $99$; a multiplier ending in $0$ makes every product end in $0$, so two products would bring two zeros, which removes $30$, $60$ and $90$. Of the remaining $27$ multipliers, the exhaustive check finds only $13$ in use: $3,6,9,12,15,18,21,24$, $27,36,39,45,48$. The published programs do not use these facts; a faster program could, for instance, skip every cut whose gcd is not divisible by $3$.

9. The factor 0

The statement does not require positive factors, and the published test admits a block consisting of the single digit $0$, the product of $n$ and the factor $0$, as in the representation $3\times(4,0,1579862)$ of the worked example. A factor $0$ and its product both have one digit, so Section 7 does not apply and longer multipliers appear, such as $41579862\times(3,0)$ with the number $1247395860$ and the input $4157986230$. The factor $0$ never comes first, since the number would then begin with $0$, and merging it into the factor before it, $a\Vert0=10a$, changes neither concatenation. So every representation with a factor $0$ has just two factors or comes from one with positive factors by splitting off the final $0$ of a factor, as $3\times(40,1579862)$ gives $3\times(4,0,1579862)$. The answer does not depend on this reading: the largest valid number is the same either way, and its only representation uses positive factors.

How the Code Works

The C++ program ^[9] starts in main; parse_arguments accepts only --skip-checkpoints. Without it, run_checkpoints checks with is_pandigital_1_to_9 that $6\cdot1273$ and $6\cdot9854$ reproduce the statement's example, then runs solve and re-checks its result with is_pandigital_0_to_9 and output_has_valid_input; main then runs solve again and prints the result, so a default run searches twice.

solve implements Section 5: a std::array holds the digits $9,8,\dots,0$, std::prev_permutation steps through the arrangements, those starting with $0$ are skipped, and the first ten-character string accepted by output_has_valid_input is returned through std::stoull as a 64-bit u64, since a ten-digit value can exceed a 32-bit int.

output_has_valid_input implements Sections 2 and 3. A split_mask from $1$ to $511$ chooses the cut, bit $b$ meaning a cut after digit $b+1$; masks with a block of several digits starting with '0' are skipped, and the blocks, at most nine digits each, are parsed into an int with std::stoi. std::gcd combines them, collect_divisors finds the divisors of $g$ by trial division up to $\sqrt g$ and sorts them in decreasing order, and for each divisor std::to_string joins the multiplier and the quotients for is_pandigital_0_to_9, which wants ten characters with every digit once. The checks for fewer than two blocks, for a divisor $0$ and for divisibility never trigger.

The Python program mirrors these functions without checkpoints; its solve builds sorted(permutations(range(10)), reverse=True), a list of all $3\,628\,800$ arrangements in decreasing order, although permutations already emits them in increasing order. ^[8] Java has no checkpoints either: hasValid follows output_has_valid_input with its own gcd and divisors, and prevPerm is the classical next-permutation algorithm with every comparison reversed. It finds the last position $i$ with $a_i\gt a_{i+1}$, swaps $a_i$ with the last later entry smaller than it and reverses the tail. ^[7] Both test pandigital strings by sorting their characters, where C++ counts digits, and print the winning string itself, so no ten-digit integer is needed; Java's blocks of at most nine digits fit into an int.

Complexity and Verification

Without early stops, the test would try $511$ masks for each of the $3\,265\,920$ candidates, dropping a mask at its first forbidden block; a candidate ending in $0$ has $511$ admissible cuts and any other $383$. This gives the numbers of masks and of admissible cuts:

$$\begin{aligned}9\cdot9!\cdot511&=1\,668\,885\,120,\\ 9!\cdot511+8\cdot9!\cdot383&=1\,297\,296\,000.\end{aligned}$$

An admissible cut costs the parsing and gcd of at most ten blocks, the trial division up to $\sqrt g$, sorting the few divisors and one string per divisor. Except for the cut that separates a final $0$ from the first nine digits, $g$ is at most the shortest nonzero block, which has at most five digits, so the trial division stops within $316$ steps; that one cut needs up to $31\,426$ steps. Both loops stop at the first success, so these counts are upper bounds. Measured on an Apple M4 Max (clang -O2, OpenJDK 17, CPython 3.11), one search takes about $1.2$ s in C++ ($2.6$ s by default, which searches twice), $1$ s in Java and $9.4$ s in Python, which first builds all $10!$ tuples in about $0.3$ s and $0.5$ GB of memory. C++ and Java hold only a few short vectors and strings.

Only the C++ program checks itself, with the checkpoints described above. For this article the result was verified independently:

Applied to all $3\,265\,920$ candidates, the published output_has_valid_input accepts exactly $6057$ numbers, the first of which in decreasing order is the number printed by all three programs.
An independent input-side search, cutting every arrangement of the ten digits in every way into a multiplier and at least two factors without leading zeros, found $19\,072$ representations of exactly these $6057$ numbers, so the test of Section 3 accepts exactly the valid numbers.
All these multipliers are multiples of $3$. The $9586$ representations with positive factors satisfy Section 7, have at most three factors, use the $13$ multipliers of Section 8 and give $4888$ numbers, the smallest being $1204739586$. Every representation with a factor $0$ arises as in Section 9.
The largest valid number has exactly one representation, and it uses positive factors.

Footnotes and References

The references below supply background facts; the proofs and all counts are derived or computed in this article.

Project Euler 170 — Pandigital Concatenating Products. The official statement shows that 6 and (1273, 9854) give the concatenated product 763859124 and the input concatenation 612739854, both 1 to 9 pandigital, and asks for the largest 0 to 9 pandigital 10-digit concatenated product of an integer with two or more other integers whose input concatenation is also a 0 to 9 pandigital 10-digit number.
Wikipedia — Pandigital number. Names 1023456789 as the smallest base-10 pandigital number and notes that the digits 0 to 9 add up to 45, passing the divisibility rules for 3 and 9.
OEIS A050278. The numbers using each digit 0 to 9 once: a finite sequence of 9·9! = 3265920 terms, from 1023456789 to 9876543210.
Wikipedia — Casting out nines. A number and its digit sum leave the same remainder modulo 9, which is used to check sums and products.
Wikipedia — Greatest common divisor. Every common divisor of two integers divides their gcd, gcd(a, 0) = |a|, and the gcd is associative, so it extends to several numbers.
cppreference — std::prev_permutation. Rearranges a range into the lexicographically previous permutation and returns false when there is none.
Wikipedia — Permutation, generation in lexicographic order. The in-place next-permutation algorithm attributed to Narayana Pandita: find the last ascent, swap its first entry with the last larger entry after it, reverse the tail.
Python — itertools.permutations. The tuples are emitted in lexicographic order according to the order of the input.
C++ — Euler170.cpp. The linked immutable C++ revision contains the functions described above and is the implementation record for this article; the exhaustive cross-checks are not part of it.

Problem 170 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    bool run_checkpoints = true;
};

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

bool is_pandigital_0_to_9(const std::string& s) {
    if (s.size() != 10U) {
        return false;
    }
    std::array<int, 10> freq{};
    for (char c : s) {
        if (c < '0' || c > '9') {
            return false;
        }
        ++freq[static_cast<std::size_t>(c - '0')];
    }
    for (int f : freq) {
        if (f != 1) {
            return false;
        }
    }
    return true;
}

bool is_pandigital_1_to_9(const std::string& s) {
    if (s.size() != 9U) {
        return false;
    }
    std::array<int, 10> freq{};
    for (char c : s) {
        if (c < '1' || c > '9') {
            return false;
        }
        ++freq[static_cast<std::size_t>(c - '0')];
    }
    for (int d = 1; d <= 9; ++d) {
        if (freq[static_cast<std::size_t>(d)] != 1) {
            return false;
        }
    }
    return true;
}

void collect_divisors(const int n, std::vector<int>& divisors) {
    divisors.clear();
    for (int d = 1; static_cast<long long>(d) * d <= n; ++d) {
        if (n % d != 0) {
            continue;
        }
        divisors.push_back(d);
        if (d * d != n) {
            divisors.push_back(n / d);
        }
    }
    std::sort(divisors.begin(), divisors.end(), std::greater<int>());
}

bool output_has_valid_input(const std::string& output) {
    std::vector<int> divisors;

    for (int split_mask = 1; split_mask < (1 << 9); ++split_mask) {
        std::vector<int> products;
        int start = 0;
        bool good_partition = true;
        for (int bit = 0; bit < 9; ++bit) {
            if (((split_mask >> bit) & 1) == 0) {
                continue;
            }
            const int end = bit + 1;
            if (output[static_cast<std::size_t>(start)] == '0' && (end - start) > 1) {
                good_partition = false;
                break;
            }
            products.push_back(std::stoi(output.substr(static_cast<std::size_t>(start),
                                                       static_cast<std::size_t>(end - start))));
            start = end;
        }
        if (!good_partition) {
            continue;
        }
        if (output[static_cast<std::size_t>(start)] == '0' &&
            (static_cast<int>(output.size()) - start) > 1) {
            continue;
        }
        products.push_back(std::stoi(output.substr(static_cast<std::size_t>(start))));
        if (products.size() < 2U) {
            continue;
        }

        int g = products.front();
        for (int value : products) {
            g = std::gcd(g, value);
        }

        collect_divisors(g, divisors);
        for (int multiplier : divisors) {
            if (multiplier == 0) {
                continue;
            }

            std::string input_concat = std::to_string(multiplier);
            bool divisible = true;
            for (int value : products) {
                if (value % multiplier != 0) {
                    divisible = false;
                    break;
                }
                input_concat += std::to_string(value / multiplier);
            }
            if (!divisible) {
                continue;
            }
            if (is_pandigital_0_to_9(input_concat)) {
                return true;
            }
        }
    }

    return false;
}

u64 solve() {
    std::array<int, 10> digits{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    do {
        if (digits[0] == 0) {
            continue;
        }
        std::string output;
        output.reserve(10);
        for (int d : digits) {
            output.push_back(static_cast<char>('0' + d));
        }

        if (output_has_valid_input(output)) {
            return static_cast<u64>(std::stoull(output));
        }
    } while (std::prev_permutation(digits.begin(), digits.end()));

    return 0;
}

bool run_checkpoints() {
    const int k = 6;
    const int a = 1273;
    const int b = 9854;
    const std::string product_concat = std::to_string(k * a) + std::to_string(k * b);
    const std::string input_concat = std::to_string(k) + std::to_string(a) + std::to_string(b);
    if (!is_pandigital_1_to_9(product_concat) || !is_pandigital_1_to_9(input_concat)) {
        std::cerr << "Checkpoint failed for 1-to-9 sample" << '\n';
        return false;
    }

    const u64 ans = solve();
    const std::string ans_s = std::to_string(ans);
    if (!is_pandigital_0_to_9(ans_s) || !output_has_valid_input(ans_s)) {
        std::cerr << "Checkpoint failed for final candidate validation" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve() << '\n';
    return 0;
}

Python

from itertools import permutations
from math import gcd

def is_pandigital_0_to_9(s):
    return len(s) == 10 and sorted(s) == list('0123456789')

def collect_divisors(n):
    divs = []
    d = 1
    while d * d <= n:
        if n % d == 0:
            divs.append(d)
            if d * d != n:
                divs.append(n // d)
        d += 1
    divs.sort(reverse=True)
    return divs

def output_has_valid_input(output):
    for split_mask in range(1, 1 << 9):
        products = []
        start = 0
        good_partition = True
        for bit in range(9):
            if not ((split_mask >> bit) & 1):
                continue
            end = bit + 1
            part = output[start:end]
            if len(part) > 1 and part[0] == '0':
                good_partition = False
                break
            products.append(int(part))
            start = end
        if not good_partition:
            continue
        last = output[start:]
        if len(last) > 1 and last[0] == '0':
            continue
        products.append(int(last))
        if len(products) < 2:
            continue
        g = products[0]
        for v in products[1:]:
            g = gcd(g, v)
        for multiplier in collect_divisors(g):
            if multiplier == 0:
                continue
            input_concat = str(multiplier)
            divisible = True
            for v in products:
                if v % multiplier != 0:
                    divisible = False
                    break
                input_concat += str(v // multiplier)
            if not divisible:
                continue
            if is_pandigital_0_to_9(input_concat):
                return True
    return False

def solve():
    digits = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    # Generate all permutations in descending order
    all_perms = sorted(permutations(range(10)), reverse=True)
    for perm in all_perms:
        if perm[0] == 0:
            continue
        output = ''.join(str(d) for d in perm)
        if output_has_valid_input(output):
            return output
    return '0'

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler170 {
    static boolean isPandigital(String s) {
        if (s.length() != 10)
            return false;
        char[] c = s.toCharArray();
        Arrays.sort(c);
        return new String(c).equals("0123456789");
    }

    static List<Integer> divisors(int n) {
        List<Integer> d = new ArrayList<>();
        for (int i = 1; (long) i * i <= n; i++)
            if (n % i == 0) {
                d.add(i);
                if (i != n / i)
                    d.add(n / i);
            }
        d.sort(Collections.reverseOrder());
        return d;
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static boolean hasValid(String output) {
        int n = output.length();
        for (int mask = 1; mask < (1 << (n - 1)); mask++) {
            List<Integer> parts = new ArrayList<>();
            int start = 0;
            boolean ok = true;
            for (int bit = 0; bit < n - 1; bit++) {
                if (((mask >> bit) & 1) == 0)
                    continue;
                String p = output.substring(start, bit + 1);
                if (p.length() > 1 && p.charAt(0) == '0') {
                    ok = false;
                    break;
                }
                parts.add(Integer.parseInt(p));
                start = bit + 1;
            }
            if (!ok)
                continue;
            String last = output.substring(start);
            if (last.length() > 1 && last.charAt(0) == '0')
                continue;
            parts.add(Integer.parseInt(last));
            if (parts.size() < 2)
                continue;
            int g = parts.get(0);
            for (int p : parts)
                g = gcd(g, p);
            for (int mult : divisors(g)) {
                if (mult == 0)
                    continue;
                StringBuilder sb = new StringBuilder();
                sb.append(mult);
                boolean div = true;
                for (int p : parts) {
                    if (p % mult != 0) {
                        div = false;
                        break;
                    }
                    sb.append(p / mult);
                }
                if (div && isPandigital(sb.toString()))
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] digits = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        do {
            if (digits[0] == 0)
                continue;
            StringBuilder sb = new StringBuilder();
            for (int d : digits)
                sb.append(d);
            if (hasValid(sb.toString())) {
                System.out.println(sb);
                return;
            }
        } while (prevPerm(digits));
    }

    static boolean prevPerm(int[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] <= a[i + 1])
            i--;
        if (i < 0)
            return false;
        int j = a.length - 1;
        while (a[j] >= a[i])
            j--;
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
        for (int l = i + 1, r = a.length - 1; l < r; l++, r--) {
            t = a[l];
            a[l] = a[r];
            a[r] = t;
        }
        return true;
    }
}