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