Guess the Missing Digit
Autumn Tournament (2019)
Submission name: guess.cpp
Problem summary
An equation has the form first operator second = result, using +, −, or *. Numbers may be negative and contain question marks. All question marks stand for the same decimal digit, which must not already occur explicitly anywhere in the equation. Find the smallest digit making the equation true, or report mistake. Numbers cannot have leading zeroes or negative zero.
Source clarification. The PDF uses typographic dashes in its prose and one sample; the runnable input format uses ASCII minus (-).
Input
One equation without whitespace.
Output
The smallest valid digit, or the word mistake.
Constraints
Each number has absolute value less than 10^6. At least one question mark occurs.
Worked example
Official statement sample.
Input
789*?54=51?00?
Output
6
Solution analysis
- Find the operator by scanning past the first number, allowing a leading minus sign but otherwise accepting only digits and question marks. Split at that operator and at the equals sign. This distinguishes subtraction from negative signs on operands.
- Mark every explicitly written digit. Try the remaining digits from 0 to 9, replace every question mark, and check that each resulting number has valid decimal notation. A multi-digit magnitude cannot begin with zero, and −0 is not a valid representation.
- For each candidate, parse the three numbers and evaluate the one operation using long long. This is important because multiplying two valid six-digit operands may temporarily require about 10^12, even though each stated number is smaller than 10^6.
- For 789*?54=51?00?, digit 6 yields 789*654=516006, a true equation; 6 is absent from the explicit digits. The first successful trial is automatically the smallest valid digit.
Why it works
The operator scan uniquely separates the three number tokens under the given grammar. Every permitted replacement digit is tested in increasing order, and invalid notation is rejected before arithmetic. The arithmetic check is exactly the original equation after substitution, so a reported digit is valid and minimal; if none passes, no solution exists.
Watch out. Do not choose a digit already printed in any operand or result. Treat unary minus separately from subtraction. Reject leading zeroes after substitution, including −0. Use long long for multiplication.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The operator scan uniquely separates the three number tokens under the given grammar.
// Every permitted replacement digit is tested in increasing order, and invalid notation is rejected
// before arithmetic.
#include<array>
#include<iostream>
#include<string>
using namespace std;
bool readNumber(string token,char replacement,long long&value){
for(char&character:token){
if(character=='?'){
character=replacement;
}
}
bool negative=token[0]=='-';
size_t start=negative?1:0;
if(token[start]=='0'&&(token.size()-start>1||negative)){
return false;
}
value=0;
for(size_t i=start;i<token.size();i++){
value=value*10+token[i]-'0';
}
if(negative){
value=-value;
}
return true;
}
int main(){
string equation;
cin>>equation;
array<bool,10>used{};
for(char character:equation){
if(character>='0'&&character<='9'){
used[character-'0']=true;
}
}
size_t operation=equation[0]=='-'?1:0;
while((equation[operation]>='0'&&equation[operation]<='9')||equation[operation]=='?'){
operation++;
}
size_t equals=equation.find('=');
string first=equation.substr(0,operation);
string second=equation.substr(operation+1,equals-operation-1);
string result=equation.substr(equals+1);
for(int digit=0;digit<=9;digit++){
if(used[digit]){
continue;
}
long long a,b,expected;
char replacement=static_cast<char>('0'+digit);
if(!readNumber(first,replacement,a)||!readNumber(second,replacement,b)||
!readNumber(result,replacement,expected)){
continue;
}
long long actual;
if(equation[operation]=='+'){
actual=a+b;
}
else if(equation[operation]=='-'){
actual=a-b;
}
else{
actual=a*b;
}
if(actual==expected){
cout<<digit<<'\n';
return 0;
}
}
cout<<"mistake\n";
}