Where to Multiply
National Olympiad — Municipal round (2010 season)
Submission name: mult.cpp
Problem summary
Insert one multiplication sign between two adjacent digits of a positive three-digit number. Find the greatest product of the resulting two numbers.
Input
A three-digit integer A.
Output
The largest obtainable product.
Constraints
100 ≤ A ≤ 999.
Worked example
An independently prepared example for this explanation.
Input
358
Output
280
Solution analysis
- There are exactly two gaps in a three-digit number, so there are only two candidate products.
- A/100 and A%100 give the factors for the first gap. A/10 and A%10 give the factors for the second gap. Compute both and take the larger.
- For 358, the choices are 3 × 58 = 174 and 35 × 8 = 280. The second product wins.
Why it works
Every allowed placement is one of the two gaps. The division and remainder formulas obtain the exact factors for each placement. Taking the maximum of both products therefore gives the global maximum.
Complexity: O(1) time and O(1) extra space.
Watch out. A suffix such as 05 has numeric value 5. Do not rearrange the digits.
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;
// These are the products for the only two possible split positions.
int first = (number / 100) * (number % 100);
int second = (number / 10) * (number % 10);
cout << max(first, second) << '\n';
}