Minimum moves to sort Binary Array in increasing order by deleting Subarray
Given a binary array A[] of length N, the task is to find the minimum number of operations required so that array A is sorted in increasing order and we can perform the following operation on array A[] such as:
- Choose any subarray Ai…j(1 ? i ? j ? N) which is sorted in increasing order and remove it from A. (Both the left and right halves are merged after performing the operation)
Examples:
Input: A[] = {0, 1, 1, 1, 0}
Output: 1
?Explanation: We can use one operation to remove the sorted subarray A2…4 = {1, 1, 1} from array A .Thus, the remaining array A = {0, 0} is sorted.Input: A[] = {1, 1}
Output: 0
Approach: The problem can be solved based on the following observation:
- Deleting a sorted subarray means we delete either:
- A subarray whose characters are all the same; or
- A subarray that looks like {0, 0, …, 0, 1, …1, 1, }
- This also tells us that the final array must be of this form. In particular, a binary array is sorted if and only if it doesn’t contain {1, 0} as a subarray, so our aim is to remove all such subsequences.
Now note in a case where we have an alternating binary array, whose first character is 1 and last character is 0. This means it must look like {1, 0, 1, 0, 1, 0, …1, 0} and in particular has even length, say 2K. The minimum number of moves needed to sort such an array is simply K.
Follow the below steps to solve the problem:
- Set count = 0.
- Iterate a loop from 0 to N-2 on array A[]:
- Check if there is a sequence of ‘1’ followed by a ‘0’ exist,
- Then increment the value of the count.
- Print the value of count as an answer for the minimum number of operations required so that array A is sorted in increasing order.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find minimum number of // operations required so that array A // is sorted in increasing order int minOperation( int arr[], int n) { int count = 0; for ( int j = 0; j < n - 1; j++) { if (arr[j] == 1 && arr[j + 1] == 0) { count++; } } return count; } // Driver Code int main() { int A[] = { 0, 1, 1, 1, 0 }; int N = sizeof (A) / sizeof ( int ); // Function Call cout << minOperation(A, N); } // This code is contributed by Samim Hossain Mondal. |
Java
// Java code to implement the approach import java.io.*; import java.util.*; public class GFG { // Function to find minimum number of // operations required so that array A // is sorted in increasing order public static int minOperation( int arr[], int n) { int count = 0 ; for ( int j = 0 ; j < n - 1 ; j++) { if (arr[j] == 1 && arr[j + 1 ] == 0 ) { count++; } } return count; } // Driver Code public static void main(String[] args) { int [] A = { 0 , 1 , 1 , 1 , 0 }; int N = A.length; // Function Call System.out.println(minOperation(A, N)); } } |
Python3
# python code to implement the approach # Function to find minimum number of # operations required so that array A # is sorted in increasing order def minOperation(arr, n): count = 0 for j in range ( 0 , n - 1 ): if (arr[j] = = 1 and arr[j + 1 ] = = 0 ): count + = 1 return count # Driver Code A = [ 0 , 1 , 1 , 1 , 0 ] N = len (A) # Function Call print (minOperation(A, N)) # This code is contributed by ksam24000 |
C#
// C# code to implement the approach using System; public class GFG{ // Function to find minimum number of // operations required so that array A // is sorted in increasing order public static int minOperation( int [] arr, int n) { int count = 0; for ( int j = 0; j < n - 1; j++) { if (arr[j] == 1 && arr[j + 1] == 0) { count++; } } return count; } static public void Main (){ // Code int [] A = { 0, 1, 1, 1, 0 }; int N = A.Length; // Function Call Console.WriteLine(minOperation(A, N)); } } // This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approach // Function to find minimum number of // operations required so that array A // is sorted in increasing order function minOperation(arr, n) { let count = 0 for (let j = 0; j < n - 1; j++) { if (arr[j] == 1 && arr[j + 1] == 0) { count += 1 } } return count; } // Driver Code let A = [ 0, 1, 1, 1, 0 ] let N = A.length // Function Call console.log(minOperation(A, N)) // This code is contributed by Samim Hossain Mondal. |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
- Set count = 0.
- Check if the input array is an alternating binary array of length 2K. If it is, return K.
- Otherwise, iterate a loop from 0 to N-2 on array A[]:
- Check if there is a sequence of ‘1’ followed by a ‘0’ exist, Then increment the value of the count.
- Print the value of count as an answer for the minimum number of operations required so that array A is sorted in increasing order.
C++
// C++ code to implement the improved approach #include <bits/stdc++.h> using namespace std; // Function to check if the input array is an alternating // binary array of length 2K and return K if it is int isAlternatingBinary( int arr[], int n) { // Check if the array has odd length or contains any // element other than 0 and 1 if (n % 2 == 1 || set< int >(arr, arr + n) != set< int >({ 0, 1 })) { return -1; } // Check if the array is an alternating binary array of // length 2K for ( int i = 0; i < n; i++) { if (i % 2 == 0 && arr[i] != 1) { return -1; } if (i % 2 == 1 && arr[i] != 0) { return -1; } } return n / 2; } // Function to find minimum number of // operations required so that array A // is sorted in increasing order int minOperation( int arr[], int n) { int K = isAlternatingBinary(arr, n); if (K != -1) { return K; } int count = 0; for ( int j = 0; j < n - 1; j++) { if (arr[j] == 1 && arr[j + 1] == 0) { count++; } } return count; } // Driver Code int main() { int A[] = { 0, 1, 1, 1, 0 }; int N = sizeof (A) / sizeof ( int ); // Function Call cout << minOperation(A, N); } |
Python3
# Python code to implement the improved approach # Function to check if the input array is an alternating binary array # of length 2K and return K if it is def isAlternatingBinary(arr, n): # Check if the array has odd length or contains any element other than 0 and 1 if n % 2 = = 1 or set (arr) ! = { 0 , 1 }: return - 1 # Check if the array is an alternating binary array of length 2K for i in range (n): if i % 2 = = 0 and arr[i] ! = 1 : return - 1 if i % 2 = = 1 and arr[i] ! = 0 : return - 1 return n / / 2 # Function to find minimum number of operations required so that array A # is sorted in increasing order def minOperation(arr, n): K = isAlternatingBinary(arr, n) if K ! = - 1 : return K count = 0 for j in range (n - 1 ): if arr[j] = = 1 and arr[j + 1 ] = = 0 : count + = 1 return count # Driver Code A = [ 0 , 1 , 1 , 1 , 0 ] N = len (A) # Function Call print (minOperation(A, N)) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static int IsAlternatingBinary( int [] arr, int n) { if (n % 2 == 1 || new HashSet< int >(arr).SetEquals( new HashSet< int > { 0, 1 })) { return -1; } for ( int i = 0; i < n; i++) { if (i % 2 == 0 && arr[i] != 1) { return -1; } if (i % 2 == 1 && arr[i] != 0) { return -1; } } return n / 2; } static int MinOperation( int [] arr, int n) { int K = IsAlternatingBinary(arr, n); if (K != -1) { return K; } int count = 0; for ( int j = 0; j < n - 1; j++) { if (arr[j] == 1 && arr[j + 1] == 0) { count++; } } return count; } static void Main( string [] args) { int [] A = { 0, 1, 1, 1, 0 }; int N = A.Length; // Function Call Console.WriteLine(MinOperation(A, N)); } } |
Java
import java.util.Arrays; import java.util.HashSet; import java.util.Set; public class Main { // Function to check if the input array is an // alternating binary array of length 2K and return K if // it is public static int isAlternatingBinary( int [] arr, int n) { // Check if the array has odd length or contains any // element other than 0 and 1 if (n % 2 == 1 || ! new HashSet<Integer>() { { add( 0 ); add( 1 ); } }.equals( new HashSet<Integer>() { { for ( int i : arr) add(i); } })) { return - 1 ; } // Check if the array is an alternating binary array // of length 2K for ( int i = 0 ; i < n; i++) { if (i % 2 == 0 && arr[i] != 1 ) { return - 1 ; } if (i % 2 == 1 && arr[i] != 0 ) { return - 1 ; } } return n / 2 ; } // Function to find minimum number of // operations required so that array A // is sorted in increasing order public static int minOperation( int [] arr, int n) { int K = isAlternatingBinary(arr, n); if (K != - 1 ) { return K; } int count = 0 ; for ( int j = 0 ; j < n - 1 ; j++) { if (arr[j] == 1 && arr[j + 1 ] == 0 ) { count++; } } return count; } // Driver Code public static void main(String[] args) { int [] A = { 0 , 1 , 1 , 1 , 0 }; int N = A.length; // Function Call System.out.println(minOperation(A, N)); } } |
Javascript
function isAlternatingBinary(arr) { const n = arr.length; // Check if the array has odd length or contains any element other than 0 and 1 if (n % 2 === 1 || new Set(arr).size !== 2 || !arr.every(x => x === 0 || x === 1)) { return -1; } // Check if the array is an alternating binary array of length 2K for (let i = 0; i < n; i++) { if (i % 2 === 0 && arr[i] !== 1) { return -1; } if (i % 2 === 1 && arr[i] !== 0) { return -1; } } return n/2; } function minOperation(arr) { const K = isAlternatingBinary(arr); if (K !== -1) { return K; } let count = 0; for (let j = 0; j < arr.length - 1; j++) { if (arr[j] === 1 && arr[j + 1] === 0) { count++; } } return count; } // Example usage: const A = [0, 1, 1, 1, 0]; console.log(minOperation(A)); // Output: 1 |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us