Minimum Subarray reversals to sort given Binary Array

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 i^th 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++ Code to Implement the approach #include <bits/stdc++.h> using namespace std; // Function to count the minimum number of reversals 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 int main() {  int A[] = { 1, 0, 1, 0 };  int N = sizeof(A) / sizeof(A[0]);  // Function Call  cout << minOperations(N, A);  return 0; } 

// Java Code to Implement the approach 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  System.out.println(minOperations(N, A));  } } // This code is contributed by AnkThon 

# Python3 Code to Implement the approach # Function to count the minimum number of reversals def 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 Code if __name__ == "__main__" : A = [ 1, 0, 1, 0 ]; N = len(A); # Function Call print(minOperations(N, A)); # This code is contributed by AnkThon 

// C# Code to Implement the approach using 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 

 <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> 

2

Time Complexity: O(N)
Auxiliary Space: O(1)