Given a binary array arr[] of length N, and an integer K, the task is to find the maximum number of consecutive ones after flipping all zero in a subarray of length K.
Examples:
Input: arr[]= {0, 0, 1, 1, 1, 1, 0, 1, 1, 0}, K = 2
Output: 7
Explanation:
On taking the subarray [6, 7] and flip zero to one we get 7 consecutive ones.
Input: arr[]= {0, 0, 1, 1, 0, 0, 0, 0}, K = 3
Output: 5
Explanation:
On taking the subarray [4, 6] and flip zero to one we get 5 consecutive ones.
Approach: To solve the problem follow the steps given below:
- Initialize a variable let’s say trav which is going to iterate in the array from each position i to (0 to i-1) in the left direction and from (i+k to n-1) in the right direction.
- Check and keep an account that no zero comes in its way in any direction while iterating in the array.
- If there is a 0 then break out from the loop in that direction.
- So ultimately for i to i+k if there is any zero we are already flipping it to 1 so no need to count number of ones in this range as it will be equal to integer K only.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number of// consecutive 1's after flipping all// zero in a K length subarrayint findmax(int arr[], int n, int k){ // Initialize variable int trav, i; int c = 0, maximum = 0; // Iterate until n-k+1 as we // have to go till i+k for (i = 0; i < n - k + 1; i++) { trav = i - 1; c = 0; /*Iterate in the array in left direction till you get 1 else break*/ while (trav >= 0 && arr[trav] == 1) { trav--; c++; } trav = i + k; /*Iterate in the array in right direction till you get 1 else break*/ while (trav < n && arr[trav] == 1) { trav++; c++; } c += k; // Compute the maximum length if (c > maximum) maximum = c; } // Return the length return maximum;}// Driver codeint main(){ int k = 3; // Array initialization int arr[] = { 0, 0, 1, 1, 0, 0, 0, 0 }; // Size of array int n = sizeof arr / sizeof arr[0]; int ans = findmax(arr, n, k); cout << ans << '\n';} |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the maximum number of // consecutive 1's after flipping all // zero in a K length subarray static int findmax(int arr[], int n, int k) { // Initialize variable int trav, i; int c = 0, maximum = 0; // Iterate until n-k+1 as we // have to go till i+k for(i = 0; i < n - k + 1; i++) { trav = i - 1; c = 0; // Iterate in the array in left direction // till you get 1 else break while (trav >= 0 && arr[trav] == 1) { trav--; c++; } trav = i + k; // Iterate in the array in right direction // till you get 1 else break while (trav < n && arr[trav] == 1) { trav++; c++; } c += k; // Compute the maximum length if (c > maximum) maximum = c; } // Return the length return maximum; } // Driver code public static void main(String args[]) { int k = 3; // Array initialization int arr[] = { 0, 0, 1, 1, 0, 0, 0, 0 }; // Size of array int n = arr.length; int ans = findmax(arr, n, k); System.out.println(ans);}}// This code is contributed by Stream_Cipher |
Python3
# Python3 program for the above approach# Function to find the maximum number of# consecutive 1's after flipping all# zero in a K length subarraydef findmax(arr, n, k): # Initialize variable trav, i = 0, 0 c = 0 maximum = 0 # Iterate until n-k+1 as we # have to go till i+k while i < n - k + 1: trav = i - 1 c = 0 # Iterate in the array in left direction # till you get 1 else break while trav >= 0 and arr[trav] == 1: trav -= 1 c += 1 trav = i + k # Iterate in the array in right direction # till you get 1 else break while (trav < n and arr[trav] == 1): trav += 1 c += 1 c += k # Compute the maximum length if (c > maximum): maximum = c i += 1 # Return the length return maximum# Driver codeif __name__ == '__main__': k = 3 # Array initialization arr = [0, 0, 1, 1, 0, 0, 0, 0] # Size of array n = len(arr) ans = findmax(arr, n, k) print(ans)# This code is contributed by Mohit Kumar |
C#
// C# program for the above approach using System;class GFG{ // Function to find the maximum number of // consecutive 1's after flipping all // zero in a K length subarray static int findmax(int []arr, int n, int k) { // Initialize variable int trav, i; int c = 0, maximum = 0; // Iterate until n-k+1 as we // have to go till i+k for(i = 0; i < n - k + 1; i++) { trav = i - 1; c = 0; // Iterate in the array in left direction // till you get 1 else break while (trav >= 0 && arr[trav] == 1) { trav--; c++; } trav = i + k; // Iterate in the array in right direction // till you get 1 else break while (trav < n && arr[trav] == 1) { trav++; c++; } c += k; // Compute the maximum length if (c > maximum) maximum = c; } // Return the length return maximum; } // Driver code public static void Main() { int k = 3; // Array initialization int []arr = { 0, 0, 1, 1, 0, 0, 0, 0 }; // Size of array int n = arr.Length; int ans = findmax(arr, n, k); Console.WriteLine(ans);}}// This code is contributed by Stream_Cipher |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum number of// consecutive 1's after flipping all// zero in a K length subarrayfunction findmax(arr, n, k) { // Initialize variable let trav, i; let c = 0, maximum = 0; // Iterate until n-k+1 as we // have to go till i+k for (i = 0; i < n - k + 1; i++) { trav = i - 1; c = 0; /*Iterate in the array in left direction till you get 1 else break*/ while (trav >= 0 && arr[trav] == 1) { trav--; c++; } trav = i + k; /*Iterate in the array in right direction till you get 1 else break*/ while (trav < n && arr[trav] == 1) { trav++; c++; } c += k; // Compute the maximum length if (c > maximum) maximum = c; } // Return the length return maximum;}// Driver codelet k = 3;// Array initializationlet arr = [0, 0, 1, 1, 0, 0, 0, 0];// Size of arraylet n = arr.length;let ans = findmax(arr, n, k);document.write(ans)// This code is contributed by _saurabh_jaiswal.</script> |
Output
5
Time complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
