Given a binary array A[] of length N, the task is to find the minimum number of operations required such that no adjacent pair has the same value where in each operation we can insert either 0 or 1 at any position in the array.
Examples:
Input: A[] = {0, 0, 1, 0, 0}
Output: 2
?Explanation: We can perform the following operations to make consecutive element different in an array:
Insert 1 at index 1 in A = {0, 0, 1, 0, 0} ? {0, 1, 0, 1, 0, 0}
Insert 1 at index 5 in A = {0, 1, 0, 1, 0, 0} ? {0, 1, 0, 1, 0, 1, 0} all consecutive elements are different.Input: A[] = {0, 1, 1}
Output: 1
Approach: The problem can be solved based on the following observation:
A single move allows us to ‘break apart’ exactly one pair of equal adjacent elements of an array, by inserting either 1 between 0, 0 or 0 between 1, 1.
So, the answer is simply the number of pairs that are already adjacent and equal, i.e, positions i (1 ? i <N) such that Ai = Ai + 1, which can be computed with a simple for loop.
Follow the below steps to solve the problem:
- Initialize a variable count = 0.
- Iterate a loop for each element in A, and check if it is equal to the next element.
- If yes, increment the count by 1.
- Print the count which gives the minimum number of operations required to make consecutive elements different in an array.
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 to make// consecutive element different in// an arrayint minOperation(int arr[], int n){ int count = 0; for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { count++; } } return count;}// Driver Codeint main(){ int A[] = { 0, 0, 1, 0, 0 }; int N = sizeof(A) / sizeof(A[0]); // Function call cout << minOperation(A, N); return 0;}// This code is contributed by aarohirai2616. |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;public class GFG { // Function to find minimum number of // operations required to make // consecutive element different in // an array public static int minOperation(int arr[], int n) { int count = 0; for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { count++; } } return count; } // Driver Code public static void main(String[] args) { int[] A = { 0, 0, 1, 0, 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 to make# consecutive element different in# an arraydef minOperation(arr, n): count = 0 for i in range(0, n-1): if (arr[i] == arr[i + 1]): count = count + 1 return count# Driver Codeif __name__ == '__main__': A = [0, 0, 1, 0, 0] N = len(A) # Function call print(minOperation(A, N)) # This code is contributed by aarohirai2616. |
C#
// C# code to implement the approachusing System;public class GFG{ // Function to find minimum number of // operations required to make // consecutive element different in // an array public static int minOperation(int[] arr, int n) { int count = 0; for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { count++; } } return count; } static public void Main (){ // Code int[] A = { 0, 0, 1, 0, 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 to make// consecutive element different in// an arrayfunction minOperation(arr, n){ let count = 0; for (let i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { count += 1; } } return count;}// Driver Codelet A = [ 0, 0, 1, 0, 0 ];let N = A.length;// Function callconsole.log(minOperation(A, N));// This code is contributed by Samim Hossain Mondal. |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
