Rearranged-Digit Difference
National Olympiad — Municipal round (2015 season)
Submission name: difference.cpp
Problem summary
Rearrange the digits of a three-digit number to make the largest and smallest possible three-digit numbers. Print their difference. A leading zero is forbidden.
Input
A three-digit integer n.
Output
Largest valid rearrangement minus smallest valid rearrangement.
Constraints
100 ≤ n ≤ 999.
Worked example
An independently prepared example for this explanation.
Input
341
Output
297
Solution analysis
- There are at most six permutations of three digits, so direct enumeration is small and avoids special cases for one or two zero digits.
- Sort the digit string and use next_permutation to visit all distinct arrangements. Discard those starting with zero, convert each remaining arrangement to an integer, and maintain its minimum and maximum.
- For 341 the smallest arrangement is 134 and the largest is 431, giving 297. For 100 the only valid three-digit value is 100, so the difference is zero.
Why it works
Every rearrangement appears in the permutation enumeration. Discarding exactly the leading-zero permutations leaves all and only three-digit candidates. Taking their maximum and minimum therefore gives the specified difference.
Watch out. A permutation beginning with 0 is not a three-digit number. Repeated digits need no special handling with next_permutation.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string digits;
cin >> digits;
sort(digits.begin(), digits.end());
int smallest = 1000;
int largest = 0;
do {
// Leading-zero permutations are not three-digit numbers.
if (digits[0] != '0') {
int value = stoi(digits);
smallest = min(smallest, value);
largest = max(largest, value);
}
} while (next_permutation(digits.begin(), digits.end()));
cout << largest - smallest << '\n';
return 0;
}