Reduce insertion of 0 or 1 such that no adjoining pair has similar worth

[ad_1]

Given a binary array A[] of size N, the duty is to seek out the minimal variety of operations required such that no adjoining pair has the identical worth the place in every operation we are able to insert both 0 or 1 at any place within the array.

Examples:

Enter: A[] = {0, 0, 1, 0, 0} 
Output: 2
Rationalization:  We are able to carry out the next operations to make consecutive aspect totally 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 components are totally different.

Enter: A[] = {0, 1, 1}
Output:

Strategy: The issue may be solved based mostly on the next statement: 

A single transfer permits us to ‘break aside’ precisely one pair of equal adjoining components of an array, by inserting both 1 between 0, 0 or 0 between 1, 1. 

So, the reply is solely the variety of pairs which can be already adjoining and equal, i.e, positions i (1 ≤ i <N) such that Ai = Ai + 1, which may be computed with a easy for loop.

Comply with the beneath steps to resolve the issue:

  • Initialize a variable depend = 0.
  • Iterate a loop for every aspect in A, and examine if it is the same as the subsequent aspect.
    • If sure, increment the depend by 1.
  • Print the depend which supplies the minimal variety of operations required to make consecutive components totally different in an array.

Beneath is the implementation of the above strategy.

Java

  

import java.io.*;

import java.util.*;

  

public class GFG {

  

    

    

    

    

    public static int minOperation(int arr[], int n)

    {

        int depend = 0;

  

        for (int i = 0; i < n - 1; i++) {

            if (arr[i] == arr[i + 1]) {

                depend++;

            }

        }

        return depend;

    }

  

    

    public static void predominant(String[] args)

    {

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

        int N = A.size;

  

        

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

    }

}

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

[ad_2]

Leave a Reply