Find Zeros to be Flipped so that number of Consecutive 1’s is maximized

June 23, 2019

Given a binary array and number of zeros to be flipped, write a program to find the zeros that needs to be flipped so that the number of consecutive 1’s is maximized

Example

INPUT:
arr[] = {0, 1, 0, 1, 1, 0, 1}
zeroes= 2

OUTPUT:
The indexes are 2, 5

In the above example, we can see that when the zeroes at indexes 2 and 5 are flipped we get maximum  number of consecutiive one’s.

Time Complexity : O(n)

In this method the main idea is using the sliding window

Readers are requested to submit their codes in different languages in comment section below. .Best codes will be selected and published on website.

Algorithm

1. Initialize a variable count to keep track of number of zeros

2. Till the right pointer of the window is less than the input array

3. If the count is less than the input number of zeros, then increase the window size to the right and if we find any zero increment the count value

4. If the count is greater than the input number of zeros, then decrease the window size from the left and if we find any zero decrement the count value

5. If the window size is greater than the previous window size make it as the best window.

6. Print the zeros indexes in the best window.

Code

[code language=”language=”]

#include <bits/stdc++.h>
using namespace std;

void zeroesIndexes(int arr[],int zeroes, int n) //this function prints the zero index that should be flipped
{
int start =0, end = 0; //starting and ending of the window
int count =0; //number of zeros in window
int bestwindow =0, bestwindowstart= 0;// bestwindow size and starting point
while(end<n)
{
if(count <= zeroes) //if no of zeros is less than input zeros
{
if(arr[end]==0)
{
count++;
}
end++; //increasing window size
}
if(count > zeroes) //if no of zeros greater than input zeroes
{
if(arr[start]==0)
{
count–;
}
start++; //decreasing window size
}
if(end-start > bestwindow) //updating the best window
{
bestwindow = end-start;
bestwindowstart = start;
}

}
cout<<bestwindowstart;
cout<<"The indexes are ";
for (int i = bestwindowstart; i < bestwindow; ++i)
{
if(arr[i]==0)
cout<< i<<" ";
}
}
int main()
{
int arr[] = {0, 1, 0, 1, 1, 0, 1};
int zeroes= 2; //no of zeroes that can be flipped
int n = sizeof(arr)/sizeof(arr[0]);
zeroesIndexes(arr, zeroes, n);
return 0;
}

[/code]