## 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

## 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.

## C++ Program

```
#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;
}
```