Largest Minus Smallest Same-Length Permutation
National Olympiad — Municipal round (2015 season)
Submission name: difference.cpp
Problem summary
Rearrange the digits of an n-digit number to form the largest and the smallest n-digit numbers. Print their difference; the smallest rearrangement may not begin with zero.
Input
One positive decimal integer of length n.
Output
Largest rearrangement minus smallest n-digit rearrangement.
Constraints
2 ≤ n ≤ 18.
Worked example
Input and output for the worked example discussed below.
Input
732456198
Output
864197532
Solution analysis
- For the maximum, put digits in descending order. For the minimum, start with ascending order, but if it begins with zero, swap the first digit with the first nonzero digit. This is the smallest legal leading digit, followed by the remaining digits in ascending order.
- Convert both rearrangements to long long and subtract. At most 18 digits means every rearranged value is below 10^18 and fits signed 64-bit.
- For the sample, maximum 987654321 minus minimum 123456789 gives 864197532. With digits 102, the smallest three-digit number is 102 rather than 012: keeping the length is an essential part of this Municipal problem.
Why it works
At the first differing position, a larger digit makes a decimal number larger regardless of later digits, proving descending order maximizes it. Minimizing first chooses the smallest nonzero leading digit, then the smallest remaining digits at each position. These choices uniquely yield both extremes.
Watch out. The leading-zero rule differs from Regional task sub. Do not simply use ascending digits as the minimum when zeros exist. Avoid int and floating-point conversions.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
string digits;
cin>>digits;
sort(digits.begin(),digits.end());
string smallest=digits;
if(smallest[0]=='0'){
size_t firstNonzero=smallest.find_first_not_of('0');
// The number must retain its original decimal length.
swap(smallest[0],smallest[firstNonzero]);
}
reverse(digits.begin(),digits.end());
cout<<stoll(digits)-stoll(smallest)<<'\n';
}