Largest Common-Digit Number
National Olympiad — National round (2017 season)
Submission name: maxnumber.cpp
Problem summary
Given positive decimal integers A and B, form the largest integer using their common digits. Each digit may be used at most the smaller of its occurrence counts in A and B. If there are no common digits, report that there is no solution.
Input
Two positive integers A and B, each supplied as a decimal string.
Output
The largest possible integer, or No solution if there is no common digit.
Constraints
Each input integer has 1 to 100000 digits.
Worked example
An independently prepared example for this explanation.
Input
240134 794041
Output
4410
Solution analysis
- Read the numbers as strings rather than integers. Count the appearances of each digit in A and B in two arrays of size 10. The available number of copies of digit d is the smaller count.
- Write the available digits from 9 down to 0. Among equal-length decimal arrangements, the first differing position decides which is larger, so larger digits belong as far left as possible.
- For 240134 and 794041, the common multiset contains two 4s, one 1, and one 0. Descending order gives 4410. If the only common digit is zero, output the integer 0 once.
Why it works
No result can use more copies of any digit than the minimum input count. Using every available nonzero digit and all available zeros maximizes length and never decreases the value; arranging them in descending order is optimal by exchanging any smaller digit preceding a larger one. The all-zero case represents the integer zero.
Watch out. Do not convert the long inputs to built-in integers. Preserve repeated common digits. When only zeros are common, print 0, without leading zeros.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
string a, b;
cin >> a >> b;
array<int, 10> countA{};
array<int, 10> countB{};
for (char digit : a) {
++countA[digit - '0'];
}
for (char digit : b) {
++countB[digit - '0'];
}
bool printed = false;
// Larger common digits must occupy earlier decimal positions.
for (int digit = 9; digit >= 1; --digit) {
int copies = min(countA[digit], countB[digit]);
for (int i = 0; i < copies; ++i) {
cout << digit;
printed = true;
}
}
int zeros = min(countA[0], countB[0]);
if (printed) {
for (int i = 0; i < zeros; ++i) {
cout << '0';
}
} else if (zeros > 0) {
cout << '0';
} else {
cout << "No solution";
}
cout << '\n';
}