Sure - I’m trying not to just give you the answer, though
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
The other alternative is to convert
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
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