Find number of bits to be flipped to get maximum 1's in array

Question

We have a bit array like below

{1 0 1 0 0 1 0 1}

Number of bits in above array is 8

If we take range from [1,5] then number of bits in [1,5] range is [0 1 0 0 1].
If we flip this range then after flipping it will be [ 1 0 1 1 0]
So total number of 1's after flipping [1,5] range is [1 1 0 1 1 0 0 1] = 5

If we take range from [1,6] then number of bits in [1,6] range is [0 1 0 0 1 0].
If we flip this range then after flipping it will be [ 1 0 1 1 0 1]
So total number of 1's after flipping [1,5] range is [1 1 0 1 1 0 1 1] = 6

So the answer is range [1,6] and after flipping we can get 6 1's in array

Is there a good algorithm that can solve this problem. I an only think of dynamic programming because this problem can be broken down into sub problems which can be combined.

Solution 1

Inspired by @Nabbs comment, there is an easy way to solve this in linear time: by reducing the problem to maximal segment sum.

Transform all 0s to 1s and all 1s to -1s. The problem is then the same as minimizing the sum of the array after transforming. (the minimal sum contains most -1s in the transformed array, which corresponds to most 1s in the original problem).

We can calculate the sum as

sum(after flipping) = sum(non-flipped) - sum(flipped part before flipping)

because the sum of the flipped part is inverted. If we now express the non-flipped part as follows:

sum(non-flipped) = sum(original array) - sum(flipped part before flipping)

we find that we need to minimize

sum(after flipping) = sum(original array) - 2 sum(flipped part before flipping)

The first part is a constant, so we really need to maximize the sum of the flipped part. This is exactly what the maximum segment sum problem does.

---

I wrote a lengthy derivation on how to solve that problem in linear time a while ago, so now I'll only share the code. Below I updated the code to also store the boundaries. I chose javascript as the language, because it is so easy to test in the browser and because I don't have to make the types of variables x and y explicit.

var A = Array(1, 0, 1, 0, 0, 1, 0, 1);
var sum = 0;

// count the 1s in the original array and
// do the 0 -> 1 and 1 -> -1 conversion
for(var i = 0; i < A.length; i++) {
    sum += A[i];
    A[i] = A[i] == 0 ? 1 : -1;        
}

// find the maximum subarray
var x = { value: 0, left: 0, right: 0 };
var y = { value: 0, left: 0 };
for (var n = 0; n < A.length; n++) {
    // update y
    if (y.value + A[n] >= 0) {
        y.value += A[n];
    } else {
        y.left = n+1;
        y.value = 0;
    }
    // update x
    if (x.value < y.value) {
        x.left = y.left;
        x.right = n;
        x.value = y.value;
    }
}

// convert the result back
alert("result = " + (sum + x.value) 
    + " in range [" + x.left + ", " + x.right + "]");

You can easily verify this in your browser. For instance in Chrome, press F12, click Console and paste this code. It should output

result = 6 in range [1, 4]

Solution 2

The solution uses Kadane's Algorithm.

We have to pick that substring where there are maximum number of 0s and minimum number of 1s, i.e., substring with max(count(0)-count(1)). So that after the flip, we can get maximum number of 1s in the final string.

Iterate over the string and keep a count. Increment this count whenever we encounter a 0 and decrement it when we encounter 1. The substring which will have the maximum value of this count will be our answer.

Here's a video by alGOds which explains the approach nicely. Do watch it if you have any doubts.

Link : https://youtu.be/cLVpE5q_-DE

Solution 3

Attempt 2.0 in O(n)

Start at the beginning of the array. Step through the array. Until you reach a 0. When you reach the first 0, set count to 0, remember the start position and continue stepping while counting: +1 for 0 and -1 for 1. If the count becomes negative, reset the count and continue until you reach the end. If you find another zero set count to 0 and repeat the previous algorithm. At the end you flip the range of the start and end position if there is one.

void Flip( int* arr , int len )
{
    int s = -1 , e = -1 , c ;
    for( int i = 0 ; i < len ; i++ )
    {
        if( arr[i] == 0 )
        {
            c = 0 ;
            s = i ; 
            e = i ;
            for( int j = i ; j < len  ; j++ , i++ )
            {
                if( arr[i] == 0 )
                    c++ ;
                else
                    c-- ;

                if( c < 0 )
                {
                    s = -1 ;
                    e = -1 ;
                    break ;
                }

                if( arr[i] == 0 )
                    e = i ;
            }
        }
    }

    if( s > -1 )
        for( int i = s ; i <= e ; i++ )
            arr[i] ^= 1 ;

    for( int i = 0 ; i < len ; i++ )
        printf("%d " , arr[i] ) ;

}


int main(void) 
{
    int a[13] = {1,0,1,1,0,0,1,0,1,1,0,1,0} ;


    Flip( a , 13 ) ;

    return 0;
}

Not thoroughly tested, there may be bugs( edge cases ) but it works in principle.

Solution 4

The following code uses the trivial algorithm and runs in O(n²).

#include <iostream>
#include <bitset>
#include <utility>

typedef std::pair<unsigned, unsigned> range_t;

template <std::size_t N>
range_t max_flip(const std::bitset<N>& bs){
  int overall_score = 0;
  range_t result = range_t{0,0};

  for(std::size_t i = 0; i < N; ++i){
    int  score = bs[i] ? -1 : 1;
    auto max   = i;

    for(std::size_t j = i + 1; j < N; ++j){
      auto new_score = score + (bs[j] ? -1 : 1);

      if(new_score > score){
        score = new_score;
        max = j;
      }
    }
    if(score > overall_score){
      overall_score = score;
      result = {i,max};
    }
  }
  return result;
}

int main(){
  std::bitset<8> bitfield(std::string("10100101"));
  range_t range = max_flip(bitfield);
  std::cout << range.first << " .. " << range.second << std::endl;
}

View more solutions

Comments

[Zeta]

Trivial O(n²) algorithm, just check all ranges (n start points -> max n endpoints).

[user3341101]

I dont think its valid for downvote as this algorithm can be done on once pass over array and @Zeta you have mentioned O(n2) which is not the optimal way.

[Maroun]

I don't understand the question. In your example, shouldn't the answer be 4? If you flip the 4 zeros, you'll get 8 ones, which is the maximum.

[user2357112]

@ᴍarounᴍaroun: You have to flip a contiguous range of bits.

[Zeta]

Well, your question is "Is there a good algorithm that can solve this problem?" Since you didn't define "good", any existing algorithm is good. If you already know a better/more optimal way, you should mention it in your question.

[Maroun]

I actually find this question very interesting. +1.

[Nabb]

I think if you replace 1s with -1s and 0s with 1s, this reduces to the maximum subarray problem.

[Frank Q.]

The question is not clear. There are 9 bits in the array. Only one flip is needed to get maximum ones that is 5. May be it should be rephrased as maximum consecutive flips to get maximum ones.

[Zeta]

By the way, the most-trivial algorithm would use O(n³): create all ranges (O(n²)) and check every range (linear in length of range). Since we have approx. n² ranges we have O(n³).

[user3341101]

try to run this giving error on range_t it should be range_t result = make_pair<int,int>(0,0);

[Zeta]

@Alien01: C++11. Works fine on 4.6.2 with -std=C++0x. Do you want a C++03 compliant version?

[user3341101]

no thanks..I edited code to make it compatible with my compiler.

[user3341101]

Since we are running two loops how this is O(n)..I suppose this is O(n2)

[this]

@Alien01 Two nested loops don't necessarily mean O(n^2). You have take a closer look at where the second loop starts. I coded in a hurry so the code is equally ugly. The seconds loop is not required if you refactor the code.

[Bernhard Barker]

Just in case @Alien01 meant O(2n), not O(n^2) (technically n2 = 2n, although n2 is commonly used to mean n^2): constant factors can be ignored in big-O notation, so O(2n) = O(n).

[this]

@Dukeling Oh, right. My algorithm is exactly O(n). Btw, you would be a great help if you could try to test it on a variety of inputs.

[user3341101]

I saw ur earlier solution and it looks quite elegant..I am having difficulties in understanding these solutions..looks quite hard for me to think and implement....can u recommend some book which is more explanatory.

[Vincent van der Weele]

@Alien01 if I remember correctly, the maximum segment problem is covered in Anne Kaldewaij's The Derivation of Algorithms, together with that whole way of working. It basically follows the way of working preached by Dijkstra (which works nicely on small problems like this one, but is pretty useless for real-life problems), so maybe Googling for Dijkstra could also give some more pointers.

[user3341101]

If we consider above example { 1 0 1 0 0 1 0 1} then after changing 0->1 and 1->-1 array will change to { -1 1 -1 1 1 -1 1 -1} . If we take max segment sum on this array then it will be 2 , index range =[3,4]. I am not able to understand how can we get maximum no of elements to be flipped from this solution.

[user3341101]

Okay so maximum subarray I can get as [3,4]= [1,1]..If I flip 3,4 indexes in original array then I will get {1 0 1 1 1 1 0 1} which means after flipping 3,4 indexe I can get 6 1's on original array.So s this right?

[Vincent van der Weele]

@Alien01 I updated the code with the boundaries and translated it to javascript to make verification easier.

[stephenbez]

In case the variables are confusing: y = maximum sub array that ends at n, x = maximum sub array seen so far.