Digit-Rearrangement Difference
National Olympiad — Municipal round
Submission name: difference.cpp
Problem summary
Rearrange all digits of the input number into the largest and smallest numbers of the same length, then subtract the smaller from the larger.
Input
One decimal number c with n digits.
Output
The difference, without leading zeros.
Constraints
2 ≤ n ≤ 50. Both rearranged numbers must have n digits.
Worked example
An independently prepared example for this explanation.
Input
1020
Output
1098
Solution analysis
- Descending digits give the maximum. For the minimum, put the smallest nonzero digit first, followed by all remaining digits in ascending order.
- Subtract decimal strings from right to left, propagating the borrow.
Why it works
At the first differing position, the greater digit determines the larger equal-length number. Greedy digit order optimizes each position; the first position cannot be zero. Ordinary column subtraction then computes the exact difference.
Watch out. Do not let the minimum begin with zero, or convert a 50-digit value to a built-in integer.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
string s;
cin>>s;
sort(s.begin(),s.end());
string lo=s;
int p=lo.find_first_not_of('0');
swap(lo[0],lo[p]);
string hi=s;
reverse(hi.begin(),hi.end());
string ans(s.size(),'0');
int borrow=0;
for(int i=(int)s.size()-1;i>=0;i--){
int d=hi[i]-lo[i]-borrow;
borrow=d<0;
if(borrow){
d+=10;
}
ans[i]=char('0'+d);
} // Exact decimal subtraction.
auto q=ans.find_first_not_of('0');
cout<<(q==string::npos?"0":ans.substr(q))<<'\n';
}