Shrink Runs of Zeros
National Olympiad — Municipal round (2024 season)
Submission name: shrink.cpp
Problem summary
A sequence of decimal digits ends with a period. Replace every maximal consecutive run of zeros by a single zero and remove the final period.
Input
A string of digits followed immediately by a period.
Output
The transformed digit string without the period.
Constraints
Between 1 and 30 digits.
Worked example
An independently prepared example for this explanation.
Input
00560770002000002.
Output
0560770202
Solution analysis
- Scan the input as characters rather than as a number, because leading zeros are meaningful. Stop when the terminating period is reached.
- Print a digit if it is nonzero, or if the previous digit was not zero. Update the previous digit even when suppressing the current one.
- In the sample, 00 becomes 0, 000 becomes 0 and 00000 becomes 0. The two consecutive sevens are kept, because only zero runs are compressed.
Why it works
The first zero of every run is printed and each later zero in the same run is suppressed. Every nonzero digit is printed, so precisely the required transformation is performed.
Complexity: O(L) time and O(1) extra space when reading characters as a stream.
Watch out. Do not compress repeated nonzero digits or remove the first zero of a run.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
char digit;
char previous = '.';
while (cin >> digit && digit != '.') {
// Suppress a zero precisely when it continues an existing zero run.
if (digit != '0' || previous != '0') {
cout << digit;
}
previous = digit;
}
cout << '\n';
}