Adding the Digit Sum
National Olympiad — Regional round (2019 season)
Submission name: cred.cpp
Problem summary
Start a sequence at n. Each next term is the preceding term plus the sum of its decimal digits. Count the terms, including n, whose value is at most m.
Input
Two positive integers n and m.
Output
The number of generated terms not exceeding m.
Constraints
1 ≤ n ≤ 1000; n ≤ m ≤ 100000.
Worked example
An independently prepared example for this explanation.
Input
33 100
Output
7
Solution analysis
- Keep the current term and a counter. While the term is at most m, count it, compute its digit sum, and add that sum to obtain the next term.
- Compute a digit sum using a temporary copy: repeatedly add copy%10 and divide copy by 10. The original term must remain intact until its digit sum has been found.
- For n=33 and m=100, the counted terms are 33,39,51,57,69,84,96. The next is 111, which exceeds 100, so the answer is seven. If n=m, the starting term is still counted.
Why it works
The maintained term is initially the first sequence term, and each update applies exactly the stated recurrence. Every term is positive and its digit sum is positive, so terms strictly increase. Thus the loop counts precisely the initial terms at most m and may stop permanently at the first larger term.
Watch out. Count the initial value and any term equal to m. Do not destroy the current value while extracting its digits.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int digitSum(int value) {
int sum = 0;
while (value > 0) {
sum += value % 10;
value /= 10;
}
return sum;
}
int main() {
int current, maximum;
cin >> current >> maximum;
int count = 0;
while (current <= maximum) {
++count;
// The helper takes a copy, preserving the current term for this addition.
current += digitSum(current);
}
cout << count << '\n';
}