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

2 Likes

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

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

Edit:

Now I need to go and get some food

1 Like