Maximum Difference of Cyclic Numbers
Autumn Tournament (2015)
Submission name: twostr.cpp
Problem summary
Rotate each of two decimal strings independently. Rotations beginning with zero are invalid. Find the largest possible difference x−y between a valid rotation of the first string and a valid rotation of the second.
Input
Two digit strings s and t, each beginning with a nonzero digit.
Output
The maximum difference, without leading zeros; it may be negative.
Constraints
1 ≤ |s|,|t| ≤ 3000.
Worked example
Original statement sample.
Input
25 12
Output
40
Solution analysis
- The choices of x and y are independent. Therefore maximize x and minimize y separately. All rotations of one string have the same length, so lexicographic string comparison is also numeric comparison when leading zeros are excluded.
- Enumerate every rotation of s, retaining the greatest valid one, and every rotation of t, retaining the smallest valid one. Their lengths may differ and3000digits do not fit in built-in integer types. Compare their lengths and then lexicographically to decide the sign.
- Subtract the smaller magnitude from the larger with the usual right-to-left borrowing algorithm. Remove leading zeros and print a minus sign only for a nonzero negative result. For25 and12 the extremes are52 and12, giving40; for1 and100 the only minimum valid second rotation is100, giving−99.
Why it works
For every admissible pair, x≤maxX and y≥minY, so x−y≤maxX−minY; choosing those two extremes attains the bound. Rotation enumeration finds them exactly, and decimal borrowing computes their exact difference independently of machine integer limits.
Watch out. Ignore rotations with leading zero even when minimizing. Compare magnitudes by length before lexicographic order. A negative answer is permitted, but −0 is not.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
string extremeRotation(const string&text,bool maximum){
string best;
for(int start=0;start<static_cast<int>(text.size());start++){
if(text[start]=='0'){
continue;
}
string candidate=text.substr(start)+text.substr(0,start);
if(best.empty()||(maximum?candidate>best:candidate<best)){
best=candidate;
}
}
return best;
}
string subtract(const string&larger,const string&smaller){
string answer;
int borrow=0;
int j=static_cast<int>(smaller.size())-1;
for(int i=static_cast<int>(larger.size())-1;i>=0;i--){
int digit=larger[i]-'0'-borrow;
if(j>=0){
digit-=smaller[j]-'0';
j--;
}
borrow=digit<0;
if(borrow){
digit+=10;
}
answer.push_back(static_cast<char>('0'+digit));
}
while(answer.size()>1&&answer.back()=='0'){
answer.pop_back();
}
reverse(answer.begin(),answer.end());
return answer;
}
int main(){
string first;
string second;
cin>>first>>second;
string maximum=extremeRotation(first,true);
string minimum=extremeRotation(second,false);
// Magnitudes can have different lengths, so compare length first.
bool negative=maximum.size()<minimum.size()||(maximum.size()==minimum.size()&&maximum<minimum);
string answer=negative?subtract(minimum,maximum):subtract(maximum,minimum);
if(negative&&answer!="0"){
cout<<'-';
}
cout<<answer<<'\n';
}