Count Digit Circles after Arithmetic
National Olympiad — Municipal round (2017 season)
Submission name: circles.cpp
Problem summary
Apply +,−,or* to a and b. Count circular holes in the decimal result:0,6,9 have one,8 has two, and other digits have none.
Input
a, then b, then the operator.
Output
The number of digit circles.
Constraints
0 < a,b < 10^9; b≤a.
Worked example
Input and output for the worked example discussed below.
Input
55 13 +
Output
3
Solution analysis
- First evaluate the requested operation using long long. The maximum product is below10^18 and therefore fits signed64-bit. Since b≤a, subtraction is nonnegative.
- Use a ten-entry table for each digit’s circle count. Repeatedly take result%10, add the corresponding table value, and divide by10. A do-while loop handles result0 as the written digit0.
- The sample computes55+13=68. Digit6 contributes one circle and8 contributes two, producing3. If equal inputs are subtracted, the result0 still contributes one circle.
Why it works
The arithmetic step computes the required result exactly. Remainder/division extracts every decimal digit once, and summing the fixed per-digit contributions is the definition of the answer.
Complexity: O(log(result+1)) time and O(1) space.
Watch out. Do not omit the representation0, give8 only one circle, or multiply in32-bit arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
long long a;
long long b;
char operation;
cin>>a>>b>>operation;
long long result=operation=='+'?a+b:operation=='-'?a-b:a*b;
const int circles[10]={1,0,0,0,0,0,1,0,2,1};
int answer=0;
// Zero itself is a one-digit result and must be inspected.
do{
answer+=circles[result%10];
result/=10;
}
while(result>0);
cout<<answer<<'\n';
}