Given a binary array arr[] of size N and a positive integer K, the task is to find the minimum number of times any subarray of size K from the given array arr[] is required to be flipped to make all array elements equal to 1. If it is not possible to do so, then print “-1”.
Examples:
Input: arr[] = {0, 1, 0}, K = 1
Output: 2
Explanation:
Perform the operation in the following order:
Operation 1: Flip all elements present in the subarray {arr[0]}. Now, the array modifies to {1, 1, 0}.
Operation 2: Flip all elements present in the subarray {arr[2]}. Now the array modifies to {1, 1, 1}.
Therefore, the total number of operations required is 2.Input: arr[] = {1, 1, 0}, K = 2
Output: -1
Approach: Follow the steps below to solve the problem:
- Initialize an auxiliary array, say isFlipped[] of size N.
- Initialize a variable, say ans, to store the minimum number of K-length subarray flips required.
- Traverse the given array arr[] using a variable i and perform the following steps:
- If the value of i is greater than 0, then update the value of isFlipped[i] as (isFlipped[i] + isFlipped[i – 1])%2.
- Check if the current element needs to be flipped, i.e. if the value of A[i] is 0 and isFlipped[i] is not set OR, the value of A[i] is 1 and isFlipped[i] is set, then perform the following steps:
- If such a K-length subarray is not possible, then print “-1” and break out of the loop, as it is impossible to make all array elements equal to 1.
- Increment ans and isFlipped[i] by 1, and decrement isFlipped[i + K] by 1.
- Otherwise, continue to the next iteration.
- After completing the above steps, if all array elements can be made 1, then print the value of ans as the result.
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 minimum number // K-length subarrays required to be // flipped to make all array elements 1 void minimumOperations(vector<int>& A, int K) { // Stores whether an element // can be flipped or not vector<int> isflipped(A.size(), 0); // Store the required number of flips int ans = 0; // Traverse the array, A[] for (int i = 0; i < A.size(); i++) { // Find the prefix sum // for the indices i > 0 if (i > 0) { isflipped[i] += isflipped[i - 1]; isflipped[i] %= 2; } // Check if the current element // is required to be flipped if (A[i] == 0 && !isflipped[i]) { // If subarray of size K // is not possible, then // print -1 and return if ((A.size() - i + 1) <= K) { cout << -1; return; } // Increment ans by 1 ans++; // Change the current // state of the element isflipped[i]++; // Decrement isFlipped[i + K] isflipped[i + K]--; } else if (A[i] == 1 && isflipped[i]) { // If subarray of size K // is not possible, then // print -1 and return if ((A.size() - i + 1) <= K) { cout << -1; return; } // Increment ans by 1 ans++; // Change the current // state of the element isflipped[i]++; // Decrement isFlipped[i+K] isflipped[i + K]--; } } // Print the result cout << ans; } // Driver Code int main() { vector<int> arr = { 0, 1, 0 }; int K = 1; minimumOperations(arr, K); return 0; } |
Java
// Java program for the above approach class GFG { // Function to find the minimum number // K-length subarrays required to be // flipped to make all array elements 1 static void minimumOperations(int[] A, int K) { // Stores whether an element // can be flipped or not int[] isflipped = new int[A.length+1]; // Store the required number of flips int ans = 0; // Traverse the array, A[] for (int i = 0; i < A.length; i++) { // Find the prefix sum // for the indices i > 0 if (i > 0) { isflipped[i] += isflipped[i - 1]; isflipped[i] %= 2; } // Check if the current element // is required to be flipped if (A[i] == 0 && isflipped[i] == 0) { // If subarray of size K // is not possible, then // print -1 and return if ((A.length - i + 1) <= K) { System.out.println(-1); return; } // Increment ans by 1 ans++; // Change the current // state of the element isflipped[i]++; // Decrement isFlipped[i + K] isflipped[i + K]--; } else if (A[i] == 1 && isflipped[i] != 0) { // If subarray of size K // is not possible, then // print -1 and return if ((A.length - i + 1) <= K) { System.out.println(-1); return; } // Increment ans by 1 ans++; // Change the current // state of the element isflipped[i]++; // Decrement isFlipped[i+K] isflipped[i + K]--; } } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { int[] arr = {0, 1, 0}; int K = 1; minimumOperations(arr, K); } } // This code is contributed by user_qa7r. |
Python3
# Python3 program for the above approach # Function to find the minimum number # K-length subarrays required to be # flipped to make all array elements 1 def minimumOperations(A, K): # Stores whether an element # can be flipped or not isflipped = [0] * (len(A) + 1) # Store the required number of flips ans = 0 # Traverse the array, A[] for i in range(len(A)): # Find the prefix sum # for the indices i > 0 if (i > 0): isflipped[i] += isflipped[i - 1] isflipped[i] %= 2 # Check if the current element # is required to be flipped if (A[i] == 0 and not isflipped[i]): # If subarray of size K # is not possible, then # print -1 and return if ((len(A) - i + 1) <= K): print(-1) return # Increment ans by 1 ans += 1 # Change the current # state of the element isflipped[i] += 1 # Decrement isFlipped[i + K] isflipped[i + K] -= 1 elif (A[i] == 1 and isflipped[i]): # If subarray of size K # is not possible, then # print -1 and return if ((len(A) - i + 1) <= K): print(-1) return # Increment ans by 1 ans += 1 # Change the current # state of the element isflipped[i] += 1 # Decrement isFlipped[i+K] isflipped[i + K] -= 1 # Print the result print(ans) # Driver Code if __name__ == "__main__": arr = [0, 1, 0] K = 1 minimumOperations(arr, K) # This code is contributed by ukasp |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the minimum number // K-length subarrays required to be // flipped to make all array elements 1 static void minimumOperations(List<int> A, int K) { // Stores whether an element // can be flipped or not List<int> isflipped = new List<int>(); for(int i = 0; i < A.Count + 1; i++) isflipped.Add(0); // Store the required number of flips int ans = 0; // Traverse the array, A[] for(int i = 0; i < A.Count; i++) { // Find the prefix sum // for the indices i > 0 if (i > 0) { isflipped[i] += isflipped[i - 1]; isflipped[i] %= 2; } // Check if the current element // is required to be flipped if (A[i] == 0 && isflipped[i] == 0) { // If subarray of size K // is not possible, then // print -1 and return if ((A.Count - i + 1) <= K) { Console.Write(-1); return; } // Increment ans by 1 ans += 1; // Change the current // state of the element isflipped[i] += 1; // Decrement isFlipped[i + K] isflipped[i + K] -= 1; } else if (A[i] == 1 && isflipped[i] != 0) { // If subarray of size K // is not possible, then // print -1 and return if ((A.Count - i + 1) <= K) { Console.Write(-1); return; } // Increment ans by 1 ans += 1; // Change the current // state of the element isflipped[i] += 1; // Decrement isFlipped[i+K] isflipped[i + K] -= 1; } } // Print the result Console.WriteLine(ans); } // Driver Code public static void Main() { List<int> arr = new List<int>(){ 0, 1, 0 }; int K = 1; minimumOperations(arr, K); } } // This code is contributed by bgangwar59 |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum number // K-length subarrays required to be // flipped to make all array elements 1 function minimumOperations(A, K) { // Stores whether an element // can be flipped or not let isflipped = []; for (let i = 0; i < A.length + 1; i++) { isflipped[i] =0; } // Store the required number of flips let ans = 0; // Traverse the array, A[] for (let i = 0; i < A.length; i++) { // Find the prefix sum // for the indices i > 0 if (i > 0) { isflipped[i] += isflipped[i - 1]; isflipped[i] %= 2; } // Check if the current element // is required to be flipped if (A[i] == 0 && isflipped[i] == 0) { // If subarray of size K // is not possible, then // print -1 and return if ((A.length - i + 1) <= K) { document.write(-1); return; } // Increment ans by 1 ans++; // Change the current // state of the element isflipped[i]++; // Decrement isFlipped[i + K] isflipped[i + K]--; } else if (A[i] == 1 && isflipped[i] != 0) { // If subarray of size K // is not possible, then // print -1 and return if ((A.length - i + 1) <= K) { document.write(-1); return; } // Increment ans by 1 ans++; // Change the current // state of the element isflipped[i]++; // Decrement isFlipped[i+K] isflipped[i + K]--; } } // Print the result document.write(ans); } // Driver Code let arr = [ 0, 1, 0 ]; let K = 1; minimumOperations(arr, K); </script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach 2:- Sliding Window
C++
#include <bits/stdc++.h> using namespace std; int minKBitFlips(int A[], int K, int N) { // store previous flip events queue<int> flip; int count = 0; for (int i = 0; i < N; i++) { // remove an item which is out range of window. if (flip.size() > 0 && (i - flip.front() >= K)) { flip.pop(); } /* In a window, if A[i] is a even number with even times flipped, it need to be flipped again. On other hand,if A[i] is a odd number with odd times flipped, it need to be flipped again. */ if (A[i] % 2 == flip.size() % 2) { if (i + K - 1 >= N) { return -1; } flip.push(i); // insert count++; } } return count; } int main() { int A[] = { 0, 1, 0 }; int N = sizeof(A) / sizeof(A[0]); int K = 1; int ans = minKBitFlips(A, K, 3); cout << ans; return 0; } // This code is contributed by divyeshrabadiya07. |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { static int minKBitFlips(int[] A, int K) { // store previous flip events Queue<Integer> flip = new LinkedList<>(); int count = 0; for (int i = 0; i < A.length; i++) { // remove an item which is out range of window. if (!flip.isEmpty() && (i - flip.peek() >= K)) { flip.poll(); } /* In a window, if A[i] is a even number with even times flipped, it need to be flipped again. On other hand,if A[i] is a odd number with odd times flipped, it need to be flipped again. */ if (A[i] % 2 == flip.size() % 2) { if (i + K - 1 >= A.length) { return -1; } flip.offer(i); // insert count++; } } return count; } public static void main(String[] args) { int[] A = { 0, 1, 0 }; int K = 1; int ans = minKBitFlips(A, K); System.out.println(ans); } } |
Python3
def minKBitFlips(A, K, N): # Store previous flip events flip = [] count = 0 for i in range(N): # Remove an item which is out range of window. if (len(flip) > 0 and (i - flip[0] >= K)): flip.pop(0) """ In a window, if A[i] is a even number with even times flipped, it need to be flipped again. On other hand,if A[i] is a odd number with odd times flipped, it need to be flipped again. """ if (A[i] % 2 == len(flip) % 2): if (i + K - 1 >= N): return -1 # Insert flip.append(i) count += 1 return count # Driver code A = [ 0, 1, 0 ] N = len(A) K = 1 ans = minKBitFlips(A, K, 3) print(ans) # This code is contributed by rameshtravel07 |
C#
using System; using System.Collections; class GFG { static int minKBitFlips(int[] A, int K) { // store previous flip events Queue flip = new Queue(); int count = 0; for (int i = 0; i < A.Length; i++) { // remove an item which is out range of window. if (flip.Count > 0 && (i - (int)flip.Peek() >= K)) { flip.Dequeue(); } /* In a window, if A[i] is a even number with even times flipped, it need to be flipped again. On other hand,if A[i] is a odd number with odd times flipped, it need to be flipped again. */ if (A[i] % 2 == flip.Count % 2) { if (i + K - 1 >= A.Length) { return -1; } flip.Enqueue(i); // insert count++; } } return count; } static void Main() { int[] A = { 0, 1, 0 }; int K = 1; int ans = minKBitFlips(A, K); Console.WriteLine(ans); } } // This code is contributed by mukesh07. |
Javascript
<script> function minKBitFlips(A,K) { // store previous flip events let flip = []; let count = 0; for (let i = 0; i < A.length; i++) { // remove an item which is out range of window. if (flip.length!=0 && (i - flip[0] >= K)) { flip.shift(); } /* In a window, if A[i] is a even number with even times flipped, it need to be flipped again. On other hand,if A[i] is a odd number with odd times flipped, it need to be flipped again. */ if (A[i] % 2 == flip.length % 2) { if (i + K - 1 >= A.length) { return -1; } flip.push(i); // insert count++; } } return count; } let A=[0, 1, 0 ]; let K = 1; let ans = minKBitFlips(A, K); document.write(ans); // This code is contributed by avanitrachhadiya2155 </script> |
Output
2
Complexity Analysis:-
Time Complexity: O(N), where N is the length of the array.
Space Complexity: O(N).
Approach 3:- Greedy
C++
#include <bits/stdc++.h> using namespace std; int minKBitFlips(int A[], int K, int N) { int temp[N]; memset(temp, 0, N); int count = 0; int flip = 0; count++; for (int i = 0; i < N; ++i) { flip ^= temp[i]; if (A[i] == flip) { // If we must flip the // subarray starting here... count++; // We're flipping the subarray from // A[i] to A[i+K-1] if (i + K > N) { return -1; // If we can't flip the // entire subarray, its // impossible } flip ^= 1; if (i + K < N) { temp[i + K] ^= 1; } } } return count; } int main() { int A[] = { 0, 1, 0 }; int N = sizeof(A) / sizeof(A[0]); int K = 1; int ans = minKBitFlips(A, K, N); cout << ans; return 0; } // This code is contributed by suresh07. |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { static int minKBitFlips(int[] A, int K) { int[] temp = new int[A.length]; int count = 0; int flip = 0; for (int i = 0; i < A.length; ++i) { flip ^= temp[i]; if (A[i] == flip) { // If we must flip the // subarray starting here... count++; // We're flipping the subarray from // A[i] to A[i+K-1] if (i + K > A.length) { return -1; // If we can't flip the // entire subarray, its // impossible } flip ^= 1; if (i + K < A.length) { temp[i + K] ^= 1; } } } return count; } public static void main(String[] args) { int[] A = { 0, 1, 0 }; int K = 1; int ans = minKBitFlips(A, K); System.out.println(ans); } } |
Python3
def minKBitFlips(A, K): temp = [0]*len(A) count = 0 flip = 0 for i in range(len(A)): flip ^= temp[i] if (A[i] == flip): # If we must flip the # subarray starting here... count += 1 # We're flipping the subarray from # A[i] to A[i+K-1] if (i + K > len(A)) : return -1 # If we can't flip the # entire subarray, its # impossible flip ^= 1 if (i + K < len(A)): temp[i + K] ^= 1 return count A = [ 0, 1, 0 ] K = 1ans = minKBitFlips(A, K) print(ans) # This code is contributed by divyesh072019. |
Javascript
<script> function minKBitFlips(A, K) { let temp = new Array(A.length); let count = 0; let flip = 0; for (let i = 0; i < A.length; ++i) { flip ^= temp[i]; if (A[i] == flip) { // If we must flip the // subarray starting here... count++; // We're flipping the subarray from // A[i] to A[i+K-1] if (i + K > A.length) { return -1; // If we can't flip the // entire subarray, its // impossible } flip ^= 1; if (i + K < A.length) { temp[i + K] ^= 1; } } } return count; } let A = [ 0, 1, 0 ]; let K = 1; let ans = minKBitFlips(A, K); document.write(ans); // This code is contributed by gfgking. </script> |
C#
/*package whatever //do not write package name here */ using System; class GFG { static int minKBitFlips(int[] A, int K) { int[] temp = new int[A.Length]; int count = 0; int flip = 0; for (int i = 0; i < A.Length; ++i) { flip ^= temp[i]; if (A[i] == flip) { // If we must flip the // subarray starting here... count++; // We're flipping the subarray from // A[i] to A[i+K-1] if (i + K > A.Length) { return -1; // If we can't flip the // entire subarray, its // impossible } flip ^= 1; if (i + K < A.Length) { temp[i + K] ^= 1; } } } return count; } public static void Main(String[] args) { int[] A = { 0, 1, 0 }; int K = 1; int ans = minKBitFlips(A, K); Console.Write(ans); } } // This code is contributed by shivanisinghss2110 |
Output
2
Complexity Analysis:-
Time Complexity: O(N), where N is the length of the array.
Space Complexity: O(N).
Related Topic: Subarrays, Subsequences, and Subsets in Array
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!
