Given a binary number you have to tell the minimum number of swaps required to aggregate all 1s at one side & all 0’s at the other side.
Its not mandatory for all 1’s to gather up on right side only. Depending upon the given binary string you have to decide 7 tell the minimum count of swaps.
Swap --> 1 swapped with 0 or vice versa irrespective of its position.
Example :
Input : 0010011011
Output : 1
Explanation :
0010011011 --> The third set bit from the LHS will be swapped with the third not set bit from the RHS.
Final Binary String : 0000011111
You have to change the given string 0010011011 into one of
0000011111 or 1111100000
Try both and see which is quickest
For each of the two targets, there’s a lower bound on the minimum number of swaps that could possibly accomplish this transformation, and it’s easy to come up with a simple strategy that performs the transformation in this minimum number of swaps. Just implement this simple strategy and see how many swaps it takes.
Sure - I’m trying not to just give you the answer, though
Let’s take the example input
0010011011
as mentioned, we want to try and transform, by swaps of (possibly non-adjacent) elements into either
0000011111
or
1111100000.
Let’s imagine we want to transform it into the former, 0000011111. Let’s compare them:
0010011011 . ^ 0000011111
We see that it certainly has (at least) one element out of place - there is a 1 (marked with the “^”) where we want a 0. Since each swap can only replace at most one out-of-place element with the correct one, it will take a minimum of 1 swap to convert 0010011011 to 0000011111.
The other alternative is to convert 0010011011 into 1111100000. Again, let’s compare them.
0010011011 ^^ ^^ 1111100000
Here, there are more elements out of place - for example, there are 4 0’s where we want 1’s. Again, since each swap can only correct at most one of these 4 out of place elements, converting 0010011011 into 1111100000 will take a minimum of 4 swaps.
Your mission is to formalise this “out of place” count, and show that where I’ve written “a minimum of X swaps” I could have written “exactly X swaps”.
