Digits Missing from N
National Olympiad — National round (2015 season)
Submission name: dig.cpp
Problem summary
Find the smallest positive k-digit integer that contains every digit absent from the decimal representation of N at least once. Other digits may also appear. Print 0 if no such integer exists.
Input
k and N; read N as a decimal string.
Output
The smallest valid k-digit number, without leading zeros, or 0.
Constraints
1 ≤ k < 30; N is positive and has at most 30 digits.
Worked example
An independently prepared example for this explanation.
Input
4 123450
Output
6789
Solution analysis
- Mark all ten digits absent from N as required. Construct the answer from left to right. At each position try digits from smallest to largest, forbidding zero at the first position.
- A trial digit is feasible if, after satisfying it when necessary, the number of still-missing digits is no larger than the number of remaining positions. Those remaining positions can contain the missing digits and then any extra zeros. Choose the first feasible digit.
- For k = 4 and N = 123450, digits 6, 7, 8 and 9 are missing. Every position is needed, so the greedy choices are exactly 6, 7, 8, 9. If only zero were missing and k were 1, no first digit could cover zero legally, and the answer would be 0.
Why it works
The feasibility condition is necessary because each remaining slot can supply at most one missing digit. It is sufficient because any remaining missing digits can be placed once each, and extra slots can be filled freely; after the first slot no leading-zero restriction remains. Selecting the smallest feasible digit at every position therefore preserves some completion and is lexicographically smallest, hence numerically smallest among k-digit numbers.
Watch out. N may not fit in a built-in integer. Digits present in N are allowed as fillers. A required zero cannot occupy the leading position.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
string n;
cin >> k >> n;
bool missing[10];
fill(missing, missing + 10, true);
for (char digit : n) {
missing[digit - '0'] = false;
}
int remaining = 0;
for (bool value : missing) {
remaining += value;
}
string answer;
for (int position = 0; position < k; ++position) {
bool chosen = false;
for (int digit = position == 0 ? 1 : 0; digit <= 9; ++digit) {
// Reserve one remaining position for each still-missing required digit.
int after = remaining - (missing[digit] ? 1 : 0);
if (after <= k - position - 1) {
answer += static_cast<char>('0' + digit);
remaining = after;
missing[digit] = false;
chosen = true;
break;
}
}
if (!chosen) {
cout << 0 << '\n';
return 0;
}
}
cout << answer << '\n';
return 0;
}