Heavy Numbers
National Olympiad — National round (2014 season)
Submission name: heavy.cpp
Problem summary
A number is heavier if its digit sum is larger. If digit sums tie, the larger number is heavier. Find the heaviest of the three given numbers.
Input
Three integers a, b and c.
Output
The heaviest number.
Constraints
10 ≤ a ≤ 99; 100 ≤ b ≤ 999; 1000 ≤ c ≤ 9999.
Worked example
An independently prepared example for this explanation.
Input
84 254 3125
Output
84
Solution analysis
- The comparison has two keys: digit sum first, numeric value second. Compute each digit sum by repeatedly adding x % 10 and dividing x by 10.
- Keep the best number so far. Replace it when the next digit sum is larger, or when the sums are equal and the next number is larger.
- For 84, 254 and 3125 the digit sums are 12, 11 and 11. Therefore 84 wins even though it is the smallest numerical value. With 264 instead of 254, both 84 and 264 have sum 12, so 264 wins.
Why it works
The two-key comparison is exactly the definition of heavier. Initially the first number is best among one number. Each comparison keeps the heavier of the current best and the next candidate, so after three candidates the best is the required answer.
Watch out. Compare digit sums before numeric values. Preserve the original number while extracting its digits.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int digitSum(int x) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int best;
cin >> best;
for (int i = 0; i < 2; ++i) {
int x;
cin >> x;
// Compare digit sum first; numeric value resolves only ties.
if (digitSum(x) > digitSum(best) || (digitSum(x) == digitSum(best) && x > best)) {
best = x;
}
}
cout << best << '\n';
return 0;
}