Table of Contents

## Problem Statement

In the “Find Zeros to be Flipped so that Number of Consecutive 1’s is Maximized” problem we have given a binary array and a number x which denotes the no. of zeros to be flipped. Write a program to find the zeros that need to be flipped so that the_number of consecutive 1’s is maximized.

## Input Format

The first and only one line containing an integer value n.

Second-line containing n numbers(0 or 1) with space-separated.

The third line containing an integer x denotes the number of zeros to be flipped.

## Output Format

Print x integers by space-separated denoting the indexes of the position in which we flip the zeros.

## Constraints

- 1<=n<=10^5
- 0<=a[i]<=1
- 1<=x<=n

## Example

7 0 1 0 1 1 0 1 2

2 5

**Explanation:** In the above example, we can see that when the zeroes at indexes 2 and 5 are flipped. We get maximum number of consecutiive ones.

## Algorithm

In this method, the main idea is to use the sliding window concept.

**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 increments 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 decrements the count value.

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

**6.** Print the zeros indexes in the best window.

## Implementation

### C++ Program to Find Zeros to be Flipped so that Number of Consecutive 1’s is Maximized

#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) { cin>>a[i]; } int x; cin>>x; int left = 0, right = 0; int temp = 0, ans = 0; int count=0; while(right<n) { if(count <= x) { if (a[right] == 0) count++; right++; } if(count>x) { if(a[left] == 0) count--; left++; } if ((right-left > ans) && (count<=x)) { ans = right-left; temp = left; } } for(int i=0;i<ans; i++) { if(a[temp+i]==0) { cout<<temp+i<< " "; } } return 0; }

### Java Program to Find Zeros to be Flipped so that Number of Consecutive 1’s is Maximized

import java.util.Scanner; class sum { public static void main(String[] args) { Scanner sr = new Scanner(System.in); int n=sr.nextInt(); int a[]= new int[n]; for(int i=0;i<n;i++) { a[i]=sr.nextInt(); } int x = sr.nextInt(); int left = 0, right = 0; int temp = 0, ans = 0; int count=0; while(right<n) { if(count <= x) { if (a[right] == 0) count++; right++; } if(count>x) { if(a[left] == 0) count--; left++; } if ((right-left > ans) && (count<=x)) { ans = right-left; temp = left; } } for(int i=0;i<ans; i++) { if(a[temp+i]==0) { System.out.print((temp+i) + " "); } } } }

6 1 0 0 1 0 1 1

4

## Complexity Analysis

### Time Complexity

**O(n)** where **n** is the size of the given array **a[]**. Here we use the concept of sliding window which takes linear time.

### Space Complexity

**O(1)** because we don’t define any auxiliary space here.