Maximum Window Digit Sum
National Olympiad — Regional round (2015 season)
Submission name: sumdig.cpp
Problem summary
Among all blocks of k consecutive integers in the inclusive range a…b, find the largest sum of every decimal digit written in that block.
Input
Positive integers a, b and k.
Output
The maximum digit sum of a length-k block.
Constraints
1 ≤ a < b ≤ 50,000,000; 2 ≤ k ≤ 10,000; k ≤ b − a + 1.
Worked example
An independently prepared example for this explanation.
Input
7932 9801 177
Output
4623
Solution analysis
- Compute the digit sum of each of the first k numbers and add them to form the first window. Recomputing all k numbers for every start would be too slow.
- When the window slides by one, only its old first number and new last number change membership. Subtract the digit sum of the outgoing number and add the digit sum of the incoming one. Maintain the largest window total.
- For the smaller illustrative range 11…48 with k = 7, window 11…17 has total 35. Sliding to 12…18 subtracts 2 and adds 9, giving 42. The maximum is 63, attained by 33…39 and 42…48.
Why it works
The initial total contains exactly the first k digit sums. Each update removes exactly the number leaving the window and adds exactly the number entering, preserving the window-sum invariant. Every valid start is visited, so the largest recorded total is the required maximum.
Watch out. Use inclusive endpoints: the last window ends at b. Do not recalculate all k sums for each window.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int digitSum(int x) {
int result = 0;
while (x > 0) {
result += x % 10;
x /= 10;
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, k;
cin >> a >> b >> k;
int window = 0;
for (int x = a; x < a + k; ++x) {
window += digitSum(x);
}
int best = window;
for (int right = a + k; right <= b; ++right) {
// Sliding removes only the outgoing number and adds only the incoming one.
window -= digitSum(right - k);
window += digitSum(right);
best = max(best, window);
}
cout << best << '\n';
return 0;
}