Given a binary string, that is it contains only 0s and 1s (number of zeros equals the number of ones) We need to make this string a sequence of alternate characters by swapping some of the bits, our goal is to minimize the number swaps.

For example, for the string "00011011" the minimum number of swaps is 2, one way to do it is:

1) swap the bits : 00011011 --->> 00010111

2) swap the bits(after the first swap) : 00010111 --->> 01010101

Note that if we are given the string "00101011" we can turn it into an alternate string starting with 0(that requires 3 swaps) and also into alternate string starting with 1.( that requires one swap - the first and the last bits ).
So the minimum in this case is one swap.

What is the most efficient way to solve it?


closed as off-topic by Stephen, Mr. Xcoder, Nick Clifford, pppery, programmer5000 Aug 19 '17 at 20:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Stephen, Mr. Xcoder, Nick Clifford, pppery, programmer5000
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ Hi. We general look for a winning criterion. A common one is code-golf, which is shortest code in bytes. However, that does not always mean most efficient - most efficient might be fastest-code. What is the winning criterion for this challenge? \$\endgroup\$ – Stephen Aug 19 '17 at 20:18
  • 3
    \$\begingroup\$ How do you arrive at an alternating sequence with just 1 swap for your 00011011 example? \$\endgroup\$ – m-chrzan Aug 19 '17 at 20:22
  • \$\begingroup\$ @m-chrzan it should be "00101011" instead of "00011011 in the final paragraph \$\endgroup\$ – Mike K Aug 19 '17 at 20:42

Python 2, 52 bytes

def f(x):v=x[::2].count("1");print min(v,len(x)/2-v)

Try it online!

  • \$\begingroup\$ The question is (very) unclear, but I believe he wants the number of swaps in the optimal case, not whether starting with 1 or 0 is better. \$\endgroup\$ – Stephen Aug 19 '17 at 20:36
  • \$\begingroup\$ @Step Hen , you are right \$\endgroup\$ – Mike K Aug 19 '17 at 22:11
  • \$\begingroup\$ @StepHen Fixed! \$\endgroup\$ – Halvard Hummel Aug 19 '17 at 22:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.