max consecutive 1 or 0 that can be obtained by flipping one bit of binary nubmer

Question

given a binary number find the maximum consecutive 1s or 0s that can be obtained by flipping only one bit (either a 1 or a 0)

the code given was

    public int getMacCon(string[] A)
    {
        int n = A.Length;
        int result = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (A[i] == A[i + 1])
                result = result + 1;
        }
        int r = -2;

        for (int i = 0; i < n; i++)
        {
            int count = 0;
            if (i > 0)
            {
                if (A[i - 1] != A[i])
                    count = count + 1;
                else
                    count = count - 1;
            }
            if (i < n - 1)
            {
                if (A[i + 1] != A[i])
                    count = count + 1;
                else
                    count = count - 1;
            }
            r = Math.Max(r, count);
        }
        return result + r;
    }

Im finding hard to figure out the logic here. specially the given below part

    for (int i = 0; i < n - 1; i++)
    {
        if (A[i] == A[i + 1])
            result = result + 1;
    }

I would highly apretiate if any one can explain me the logic in this solution. Thanks

Answer 1

Not an direct answer to your question (as Marc Gravell's answer covers it enough) but I just need to add how would I solve this instead:

1. encode your string with RLE (run length encoding)

   so you need array of b,v,n values. Where b>=0 is start position, v={0,1} is bit value and n is the count of consequent occurencies. For example something like:

   const int _max=100; // max number of bits
   int b[_max],v[_max],n[_max],bvns=0;
   

   The bvns is number of used b,v,n in the arrays. You can also use any dynamic list/template instead.

2. reset your actual solution

   You need bit position to change ix and the count of consequent bits resulting after its flip sz. Set booth to zero.

3. scan the RLE for items with n=1

   if found that means item before and after in the RLE is the same so flipping will join them. So compute the resulting size and if bigger then store as actual solution something like:

   for (int i=1;i<bvns-1;i++) // scann RLE except first and last item
    if (n[i]==1) // single bit found
     {
     l=n[i-1]+1+n[i+1]; // resulting size
     if (l>=sz) { sz=l; ix=b; } // update solution
     }
   

4. test if enlarging single sequence is not bigger

   simply:

   for (int i=0;i<bvns;i++) // scann RLE
    if (n[i]>=sz) // result is bigger?
     {
     sz=l; ix=b-1; // update solution
     if (ix<0) ix=b+n[i];
     }
   

Answer 2

The bit you've highlighted just counts the number of currently adjacent equal values, i.e. where one value (A[i]) is equal to the next (A[i+1]). It then asks (the second loop), for each value in turn, whether flipping it would increase vs decrease vs not change the number of adjacent equal values; so if a value is currently different from the one before it (A[i-1] != A[i]), a flip would be an increase - else decrease; likewise the one after it. The final result is the pre-existing number of adjacent equal values (result), plus the best delta (r) found in the sweep.

public int getMacCon(string[] A)
{
    int n = A.Length;
    int result = 0;
    // find how many adjacent values are currently in the string
    for (int i = 0; i < n - 1; i++)
    {
        // if same as the next value, that's a hit
        if (A[i] == A[i + 1])
            result = result + 1;
    }
    // worst case delta from flipping one value is that me make it
    // worse on both sides, so -2
    int r = -2;

    // now consider each value in turn
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        if (i > 0) // test value before, if not the first value
        {
            if (A[i - 1] != A[i])
                count = count + 1; // before is different; flip is incr
            else
                count = count - 1; // before is same; flip is decr
        }
        if (i < n - 1) // test value after, if not the last value
        {
            if (A[i + 1] != A[i])
                count = count + 1; // after is different; flip is incr
            else
                count = count - 1; // after is same; flip is decr
        }
        // compare that to the tracking counter, and keep the best value
        r = Math.Max(r, count);
    }
    // final result is sum of pre-existing count plus the delta
    return result + r;
}

Incidentally, an optimization might be to change the second loop test from i < n to i < n && r != 2 - i.e. stop as soon as the best possible delta is found (making it better on both sides, +2)