Equal Digit Sums, Largest Gap
National Olympiad — National round (2018 season)
Submission name: difference.cpp
Problem summary
Among pairs of positive n-digit decimal integers with equal digit sums, find the largest possible difference.
Input
One integer n.
Output
The largest difference.
Constraints
1 ≤ n ≤ 18.
Worked example
An independently prepared example for this explanation.
Input
2
Output
72
Solution analysis
- Fix a possible digit sum s from 1 through 9n. For this sum, the greatest gap is the largest n-digit number with sum s minus the smallest n-digit number with sum s.
- Build the largest by placing as much remaining sum as possible in each position from left to right. Build the smallest by placing the smallest digit that still leaves enough capacity (9 per remaining position); its first digit must be at least 1. Evaluate the difference for every s.
- For n=2, sum 10 allows the extremes 19 and 91, giving 72. Other sums cannot give a larger gap. Enumerating all sums also handles n=1, where the two extremes always coincide and the answer is zero.
Why it works
For a fixed sum, any larger earlier digit makes a decimal number larger regardless of its suffix. The maximum construction chooses the largest feasible digit; the minimum chooses the smallest feasible digit, preserving enough remaining capacity and a nonzero leading digit. They therefore give the exact extremes for that sum. Every legal pair has one enumerated sum, so the largest evaluated gap is globally optimal.
Watch out. Both numbers must have exactly n digits; the smaller one cannot start with zero. Use long long for 18-digit values.
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;
long long extreme(int n, int sum, bool largest) {
long long number = 0;
for (int position = 0; position < n; ++position) {
int remaining = n - position - 1;
int digit;
if (largest) {
digit = min(9, sum);
} else {
int minimum = position == 0 ? 1 : 0;
// Leave enough digit capacity to realize the remaining sum.
digit = max(minimum, sum - 9 * remaining);
}
number = number * 10 + digit;
sum -= digit;
}
return number;
}
int main() {
int n;
cin >> n;
long long answer = 0;
for (int sum = 1; sum <= 9 * n; ++sum) {
long long largest = extreme(n, sum, true);
long long smallest = extreme(n, sum, false);
answer = max(answer, largest - smallest);
}
cout << answer << '\n';
}