Minimum replacements for binary string to be sorted

by

Given a binary string of 0 and 1 eg. “001010”.

You can replace a 0 with 1 or a 1 with a 0.

Write an algorithm that gives the minimum number of replacements to be made in order for the binary string to be sorted (all the 0s come before the 1s).

Eg.

“0011110010” –> 3.

“0011110” –> 1

“1010110111” –> 3

I found the count of 1s and 0s. I tried to find a pivot position using the current count of 0s, beyond which all is supposed to be 1, and counted the number of divergences ie instances where we found 0 instead of 1. However I did not get the correct results.

  • Add your approach/program as well?

    – 

  • Do you have a link for submmiting a solution? I want to be sure it works

    – 

  • Please provide enough code so others can better understand or reproduce the problem.

    – 
    Bot

  • Why do say the minimum number of replacements in your second example ("0011110" --> 1) is 1? You must flip the characters at indices 2 (to '0') and 6 (to '1'), making the number of replacements 2, not 1. Since you are sorting you must end up with the same numbers of '0's and '1's you had initially, implying that the number or replacements must always be even. The same applies to your other two examples.

    – 




  • @CarySwoveland by sorting the question means any 0s should come before 1s. it does not imply that we must end up with the same numbers of ‘0’s and ‘1’s as we had initially. I agree the phrasing of the question is quite odd.

    – 

Lets iterate form left to right while keeping track of the number of 1’s to the left and number of 1’s to the right, now if you are at some index you want to sort around, you should change all ones on its left to zeroes and all zeroes on its right to ones, so the answer for it would be the sum of those 2.
Now you need to track them, to track the zeroes is just a counter, and to count the ones to the right you can count first the total number of ones and substract the number of ones not to the right.

We are given an string str of length n > 0, each character being '0' or '1'. If all characters are '0' or all characters are '1' we are finished. I therefore assume that str contains at least one '0' and one '1'.

Set count = 0.

The algorithm has two steps.

Step 1

Determine the index i of the first '1' and the index j of the last '0'

If j <= i we are finished (as all zeroes precede all ones), so we return count; else go to Step 2.

Step 2

Exchange characters at indices i and j; that is,

str[i] = '0'
str[j] = '1'

and increment count by 2.

At this point str[k] equals '0' for 0 <= k <= i, and str[k] equals '1' for j <= k <= n-1.

Go to Step 1.

Observations

At each iteration after the first:

  • determining the index of the first '1' requires a linear search that begins at index i+1 where i is the index of the first '1' found in the previous iteration; and

  • determining the index of the last '0' requires a linear search that begins at index j-1 where j is the index of the last '0' found in the previous iteration.

Note that one can determine whether the string contains all '0's or all '1's in the first iteration, in Step 1.

It follows that the time complexity of the algorithm is O(n).

Example 1

       0123456789
str="0101001010"

count = 0

First iteration

i = 1 # first '1'
j = 9 # last '0'
str[1] = '0'
str[9] = '1'
count = count + 2 #=> 2
         0123456789
str #=> '0001001011'

Second iteration

i = 3 # first '1'
j = 7 # last '0'
str[3] = '0'
str[7] = '1'
count = count + 2 #=> 4
         0123456789
str #=> "0000001111"

Third iteration

i = 6 # first '1'
j = 5 # last '0'

Since j <= i we are finished and return 4 (count).

Example 2

       0123456789
str="1011010101"

count = 0

First iteration

i = 0 # first '1'
j = 8 # last '0'
str[0] = '0'
str[8] = '1'
count = count + 2 #=> 2
         0123456789
str #=> '0011010111'

Second iteration

i = 2 # first '1'
j = 6 # last '0'
str[2] = '0'
str[6] = '1'
count = count + 2 #=> 4
         0123456789
str #=> '0001011111'

Third iteration

i = 3 # first '1'
j = 4 # last '0'
str[3] = 0
str[4] = 1
count = count + 2 #=> 6
         0123456789
str #=> '0000111111'

Fourth iteration

i = 4 # first '1'
j = 3 # last '0'

Since j <= i we are finished and return 6 (count).

Leave a Comment