Largest Binary Rearrangement
Autumn Tournament (2009)
Submission name: maxbin.cpp
Problem summary
Rearrange all digits of a supplied binary number to obtain the largest possible binary number.
Input
A binary digit string.
Output
Its digits rearranged into the maximum-value binary representation, retaining every supplied digit.
Constraints
The input contains at most 100 binary digits.
Worked example
Original statement sample.
Input
10010
Output
11000
Solution analysis
- Binary place values decrease from left to right. Thus every 1 should appear before every 0. Count the ones; the remaining characters are zeros.
- Print that many ones followed by the zeros. Keep the input as a string: even 100 binary digits need not fit in an ordinary integer, and no numerical conversion is necessary.
- The sample 10010 contains two ones and three zeros. Placing the ones in the most significant positions produces 11000.
Why it works
If a zero occurs before a one, swapping those two positions increases the value because the earlier position has larger weight. Repeating removes every such inversion and yields all ones followed by all zeros, which is therefore maximal.
Watch out. Do not parse the binary string as decimal or as a machine-sized binary integer. Preserve zeros, including an all-zero input.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int main(){
string digits;
cin>>digits;
int ones=count(digits.begin(),digits.end(),'1');
int zeros=static_cast<int>(digits.size())-ones;
// Put all larger digits in the more significant positions.
cout<<string(ones,'1')<<string(zeros,'0')<<'\n';
}