Minimize insertion of 0 or 1 such that no adjacent pair has same value

Kashish Kumar
Published: November 1, 2022

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 2 in A = {0, 0, 1, 0, 0} → {0, 1, 0, 1, 0, 0}
Insert 1 at index 6 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.

Java

  

import java.io.*;

import java.util.*;

  

public class GFG {

  

    

    

    

    

    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;

    }

  

    

    public static void main(String[] args)

    {

        int[] A = { 0, 0, 1, 0, 0 };

        int N = A.length;

  

        

        System.out.println(minOperation(A, N));

    }

}

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

Source: www.geeksforgeeks.org