Given a binary array A[] of size N, the task is to find the minimum number of subarrays that need to be reversed to sort the binary array.
Examples:
Input: N = 4, A[]: {1, 0 , 0, 1}
Output: 1
Explanation: Reverse the array from 0 to 2 to change the array to {0, 0, 1, 1}Input: N = 4, A[]: {1, 0, 1 , 0}
Output: 2
Explanation: Reverse the array from 1 to 2 and then from 0 to 3
Approach: The idea to solve the problem is as follows:
To sort A[] iterate through the array and reverse every leftmost instance of a subarray of A[] with consecutive ‘1’s and then consecutive ‘0’s.
The count of all these subarrays can be found by counting the indices where A[i] = 1 and the next element i.e., A[i+1] = 0.
Follow the steps below to implement the idea:
- Initialize a count variable with 0.
- Run a loop from 0 to N-2, and in each iteration do the following:
- If the ith element is 1 and (i+1)th element is 0 increment count by one as there is a subarray of the type [. . .1100. . . ] that needs to be reversed to sort the array.
- Return the count variable.
Below is the implementation of the above approach.
C++
// C++ Code to Implement the approach#include <bits/stdc++.h>using namespace std;// Function to count the minimum number of reversalsint minOperations(int n, int A[]){ // Declare variable to count the operations int count = 0; for (int i = 0; i < n - 1; i++) { // Whenever there is a pattern of // consecutive 1's followed by 0's // It means you have to reverse that // subarray, so increase your count by 1 if (A[i] == 1 && A[i + 1] == 0) { count++; } } // Return the count return count;}// Driver Codeint main(){ int A[] = { 1, 0, 1, 0 }; int N = sizeof(A) / sizeof(A[0]); // Function Call cout << minOperations(N, A); return 0;} |
Java
// Java Code to Implement the approachpublic class GFG { // Function to count the minimum number of reversals static int minOperations(int n, int A[]) { // Declare variable to count the operations int count = 0; for (int i = 0; i < n - 1; i++) { // Whenever there is a pattern of // consecutive 1's followed by 0's // It means you have to reverse that // subarray, so increase your count by 1 if (A[i] == 1 && A[i + 1] == 0) { count++; } } // Return the count return count; } // Driver Code public static void main (String[] args) { int A[] = { 1, 0, 1, 0 }; int N = A.length; // Function Call System.out.println(minOperations(N, A)); }}// This code is contributed by AnkThon |
Python3
# Python3 Code to Implement the approach# Function to count the minimum number of reversalsdef minOperations(n, A) : # Declare variable to count the operations count = 0; for i in range(n-1) : # Whenever there is a pattern of # consecutive 1's followed by 0's # It means you have to reverse that # subarray, so increase your count by 1 if (A[i] == 1 and A[i + 1] == 0) : count += 1; # Return the count return count;# Driver Codeif __name__ == "__main__" : A = [ 1, 0, 1, 0 ]; N = len(A); # Function Call print(minOperations(N, A)); # This code is contributed by AnkThon |
C#
// C# Code to Implement the approachusing System;public class GFG { // Function to count the minimum number of reversals static int minOperations(int n, int []A) { // Declare variable to count the operations int count = 0; for (int i = 0; i < n - 1; i++) { // Whenever there is a pattern of // consecutive 1's followed by 0's // It means you have to reverse that // subarray, so increase your count by 1 if (A[i] == 1 && A[i + 1] == 0) { count++; } } // Return the count return count; } // Driver Code public static void Main (string[] args) { int []A = { 1, 0, 1, 0 }; int N = A.Length; // Function Call Console.WriteLine(minOperations(N, A)); }}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript Code to Implement the approach // Function to count the minimum number of reversals const minOperations = (n, A) => { // Declare variable to count the operations let count = 0; for (let i = 0; i < n - 1; i++) { // Whenever there is a pattern of // consecutive 1's followed by 0's // It means you have to reverse that // subarray, so increase your count by 1 if (A[i] == 1 && A[i + 1] == 0) { count++; } } // Return the count return count; } // Driver Code let A = [1, 0, 1, 0]; let N = A.length // Function Call document.write(minOperations(N, A));// This code is contributed by rakeshsahni</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
