Multiply a Huge Number by Five
National Olympiad — Regional round (2014 season)
Submission name: popet.cpp
Problem summary
A positive integer arrives one digit per line, most significant first, ending with !. Print five times the integer without leading zeroes.
Input
One decimal digit per line, followed by a line containing !.
Output
The product by 5 on one line.
Constraints
1…100 digits; the first digit is nonzero.
Worked example
An independently prepared example for this explanation.
Input
1 2 !
Output
60
Solution analysis
- Store the digits in a string because 100 digits do not fit any standard integer type. Multiply from right to left, just as on paper.
- For each digit calculate digit*5+carry. Keep its remainder modulo 10 as the output digit and pass the quotient by 10 to the next position. Prepend a final carry if present.
- For 12, the units step gives 2*5=10, producing 0 and carry 1. The tens step gives 1*5+1=6. The result is 60.
Why it works
After each processed suffix, the stored suffix digits and carry represent exactly five times that suffix, with the carry belonging to the next position. The quotient–remainder step preserves this relation. At the end any final carry completes the decimal product.
Watch out. Do not parse the entire input as long long. Propagate carry from right to left and retain a possible new leading digit.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
using namespace std;
int main() {
string digits;
char symbol;
while (cin >> symbol && symbol != '!') {
digits += symbol;
}
int carry = 0;
for (int i = static_cast<int>(digits.size()) - 1; i >= 0; i--) {
// Carry travels from the units digit toward the most significant digit.
int product = (digits[i] - '0') * 5 + carry;
digits[i] = static_cast<char>('0' + product % 10);
carry = product / 10;
}
if (carry > 0) {
cout << carry;
}
cout << digits << '\n';
}