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

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.