Maximize the number of 0s to flip in a given binary array such that there are at least K 0s between two 1s

A binary array is a special type of array that contains only the numbers 0 and 1. In this problem, we are given a binary array and an integer K. Our task is to calculate the maximum number of 0's that can be flipped into 1's in a given binary array such that there are at least K 0's between two 1's.

ExampleExample

Input 1: arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },  K = 2

Output 1: yes

The Chinese translation of

Explanation

is:

Explanation

The 3rd and 6th indexes in the above array are the only valid indexes and can be flipped to ensure that there are at least 2 0s between the two 1s. Therefore, the resulting array is {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}

Input 2: arr[] = {0, 1, 0, 0, 0, 1}, k = 1

Output 2: 1

The Chinese translation of

Explanation

is:

Explanation

The 3rd index of the above array is the only valid flip index.

Approach

We have seen the examples given above with arrays and integers k, let us move on to the method −

The idea of ​​this method is to count the number of consecutive 0s between two 1s, and check whether it is suitable to flip some 0s to 1s between them. Suppose there are X zeros between two ones. According to observation, the number of 0s that can be flipped is (X-K) / (K 1). So, iterate through the array and record how many consecutive 0's there are between each pair of 1's. Then, add the number of 0s that can be flipped to the variable count, which is the desired response.

Let us discuss the following method step by step -

• First we will create a function called 'onesCount' which will take the given array 'arr' and integer 'K' as parameters and return the required integer 'count' value returned.

• Create variables count and lastIdx.

• Initialize the variable count with 0, which is used to store the count of fillip 0s.

• Initialize the variable lastIdx using (-(K 1)) to store the last index in the array with a value of 1.

• Use a for loop to iterate through the array, check if the current element is 1, and then verify if there are enough 0s between two consecutive 1s to add another 1. Finally, update the index value of the last 1.

• Write a condition that calculates the last segment of 0 in the array and adds it to the variable count.

• Finally, our final answer count is returned.

The Chinese translation of

Example

is:

Example

The following is a C program for calculating the maximum conversion of 0s into 1s to ensure that there are at least k 0s between two 1s.

#include <bits/stdc++.h>
using namespace std; 
// Function to find the count of the maximum number of 0s to be filliped 
int onesCount(int arr[], int n, int k){
   int count = 0; // Stores the count of 1's 
   int lastIdx = -(k + 1); // Stores the last index of value 1 
   
   // Traverse the array using for loop
   for (int i = 0; i < n; i++) { 
      // If the current element is 1
      if (arr[i] == 1) { 
      
         // Verify whether there are enough 0s between two consecutive 1s to add another 1 in between them.
         if (i - lastIdx - 1 >= 2 * (k - 1)) {
            count += (i - lastIdx - 1 - k) / (k + 1);
         } 
         lastIdx = i; // Update the last index of the value 1 of the array
      }
   } 
   
   // condition to include the last section of 0s in the array
   count += (n - lastIdx - 1) / (k + 1);
 
   // Return the answer
   return count;
} 
int main(){
   int arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }; // given array
   int N = sizeof(arr) / sizeof(arr[0]); //getting size of an array
   int K = 2; //given integer 
   
   // Call the function
   int result = onesCount(arr, N, K);    
   cout<< "The count of Maximum filliped of 0's is "<< result ;
   return 0;
}

Output

The Count of Maximum filliped of 0's is 2

Time and space complexity

The time complexity of the above code is O(N) because we only traverse the array. where N is the size of the given array.

The space complexity of the above code is O(1) because we are not using any extra space.

in conclusion

In this tutorial, we implemented a program to find the maximum number of 0s to flip in a given binary array so that there are at least K 0s between two 1s. This problem is solved by counting the number of consecutive zeros between two 1's and checking if it is suitable to flip some zeros between them. The time complexity is O(N) and the space complexity is O(1). where N is the size of the string.

The above is the detailed content of Maximize the number of 0s to flip in a given binary array such that there are at least K 0s between two 1s. For more information, please follow other related articles on the PHP Chinese website!