Select Page

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

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