Find the Number Base
Autumn Tournament (2014)
Submission name: equality.cpp
Problem summary
An equation X+Y=Z is written in an unknown base from 2 to 36. Digits 0–9 have their usual values and A–Z mean 10–35. Find the smallest base in which all digits are valid and the equation is true.
Input
A string X+Y=Z without spaces.
Output
The smallest valid base.
Constraints
Each number has at most 9 digits; the intended equation has a solution with base between 2 and 36.
Worked example
Original statement sample.
Input
2B+15A=184
Output
17
Solution analysis
- Try bases in increasing order. A digit with value d is legal only when d<base; for example B has value 11 and cannot occur in base 11. Reject a candidate as soon as any digit is invalid.
- Evaluate a numeral from left to right with value=value·base+digit. Parse the plus and equals signs once, then evaluate X, Y, and Z in each candidate base. Use long long: even 36⁹−1 fits safely, and so does a sum of two such values.
- In base 17, 2B=2·17+11=45, 15A=17²+5·17+10=384, and 184=17²+8·17+4=429. Thus 45+384=429. For 2+2=4, bases 2–4 contain an illegal digit, and base 5 is the first answer.
Why it works
Every permitted base is tested from smallest to largest. Conversion is the positional-value definition of a numeral. A candidate is accepted exactly when every digit is valid and the resulting integer equality holds, so the first accepted candidate is the smallest solution.
Watch out. Do not accept digits equal to the base. Letters are uppercase. Use 64-bit values and do not interpret the input using decimal conversion. The source asks for an answer but specifies no output for an equation having no valid base; this implementation follows the promised solvable-input model.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every permitted base is tested from smallest to largest. Conversion is the positional-
// value definition of a numeral.
#include<iostream>
#include<string>
using namespace std;
long long convert(const string&digits,int base){
long long value=0;
for(char character:digits){
int digit=character<='9'?character-'0':character-'A'+10;
if(digit>=base){
return -1;
}
value=value*base+digit;
}
return value;
}
int main(){
string equation;
cin>>equation;
size_t plus=equation.find('+');
size_t equals=equation.find('=');
string first=equation.substr(0,plus);
string second=equation.substr(plus+1,equals-plus-1);
string result=equation.substr(equals+1);
for(int base=2;base<=36;++base){
long long x=convert(first,base);
long long y=convert(second,base);
long long z=convert(result,base);
if(x>=0&&y>=0&&z>=0&&x+y==z){
cout<<base<<'\n';
return 0;
}
}
}