Largest Digit Expression
National Olympiad — Municipal round (2013 season)
Submission name: max.cpp
Problem summary
Insert either + or * into each gap of a three-digit number. Evaluate with normal multiplication precedence and find the maximum result.
Input
One three-digit number.
Output
The largest of the four expression values.
Constraints
The number is between 100 and 999.
Worked example
An independently prepared example for this explanation.
Input
128
Output
17
Solution analysis
- There are two gaps and two choices per gap, giving only four expressions. Extract hundreds a, tens b and units c.
- Evaluate a+b+c, a+b*c, a*b+c and a*b*c. Their maximum covers every possible insertion.
- For 128, the values are 11,17,10,16. The winning expression is 1+2*8 = 17.
Why it works
Each operator pair is one of the four listed cases. Every case is evaluated using multiplication before addition, so taking their maximum gives the largest attainable expression value.
Complexity: O(1) time and extra space.
Watch out. Do not evaluate a+b*c as (a+b)*c. Zero and one digits make a greedy always-multiply rule fail.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int number;
cin >> number;
int a = number / 100;
int b = number / 10 % 10;
int c = number % 10;
// These four expressions exhaust the two independent operator choices.
cout << max({a + b + c, a + b * c, a * b + c, a * b * c}) << '\n';
}