Binary Madness --> Need HELP

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

1 Like

Vague hints …

You have to change the given string 0010011011 into one of

0000011111 or

Try both and see which is quickest :slight_smile:

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.


Exactly how can I achieve this ? Would you please elaborate more ?

Sure - I’m trying not to just give you the answer, though :slight_smile:

Let’s take the example input


as mentioned, we want to try and transform, by swaps of (possibly non-adjacent) elements into either




Let’s imagine we want to transform it into the former, 0000011111. Let’s compare them:

. ^

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.

^^ ^^

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”.


Now I need to go and get some food :slight_smile:

1 Like