Given a binary string with all 0's covert it in the target string

Question

Given a binary String which represents the target state. Minimum number of flips needed to convert a same size Binary String (with all 0’s) to target state. A flip also causes all the right bits to be flipped.

e.g.

Input : 00101 (Represents Target)

Output : 3

Explanation :

00000 -> 00111 -> 00100 -> 00101

Answer 1

Two observations:

1. Flips are commutative. You'll get the same result regardless of what order you do them in.

2. At some point you have to flip the most significant bit that doesn't match

This gives us a handy greedy argument. We will always get the optimal solution by flipping the leftmost bit that needs to be flipped. At some point we have to flip that bit, and the order doesn't matter so we might as well do it first.

Implementing this to be O(N) can be tricky - if we flip everything naively we end up with an O(N) flip which gives an O(N^2) solution. We can note that in determining the true value of the current bit, we only care about the number of flips that have already occurred. If this number is odd then the value of that bit is flipped. Otherwise it is unchanged.

We can then make a final observation to make life a lot easier:

3. Flips cancel each other out. Instead of asking how many flips it takes to get from 0 to the target, let's ask how many flips it takes to get from the target to 0. Whenever the true value of a bit is not equal to zero, we simply add a flip.

Pseudocode:

result = 0
// most to least significant
for bit in bits:
    if result%2 == 0:
        if bit != 0: result += 1
    else:
        if not bit != 0: result += 1
print(result)

And to be more succinct:

bits = [0, 0, 1, 0, 1]
result = 0
for bit in bits: result += (result%2)^bit
print(result)

Output:

3

Answer 2

Input : 00101 (Represents Target) Output : 3 Explanation : 00000 -> 00111 -> 00100 -> 00101

static int minFlip(String arr) {
    String s = "00000";
    int i;
    char[] original = s.toCharArray();
    char[] bits = arr.toCharArray();
    int result = 0;
    for (i = 0; i < bits.length;) {
        if (bits[i] != original[i]) {
            for (int j = i; j < original.length; j++) {
                if (original[j] == '0') {
                    original[j] = '1';
                } else {
                    original[j] = '0';                  
                }
            }
            result++;   
        }   
        i++;
    }
    return result;
}

Answer 3

Thanks, @Primusa for the answer. Below is the code in Java for @Primusa 's answer:

    public static int getFlipsCount(String s) {
        int result = 0;
        int[] arr = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            arr[i] = Integer.valueOf(s.charAt(i) + "");
        }
        for (int i = 0; i < arr.length; i++) {
            result += (result % 2) ^ arr[i];
        }
        return result;
    }

Answer 4

In case someone wonder how to do it in cpp here's the minimal solution:

#include <iostream>
using namespace std;
int theFinalProblem(string target)
{
    int result=0;
    for(int i=0;i<target.size();i++)
        if(result%2==0 && target[i] || target[i] =='0')
            ++result;
    return result;
}
int main() {
    cout<<theFinalProblem("1010");
    return 0;
}