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 will carry out the next operations to make consecutive ingredient 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: 1
Method: The issue might be solved primarily based on the next remark:
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 are already adjoining and equal, i.e, positions i (1 ≤ i <N) such that Ai = Ai + 1, which might be computed with a easy for loop.
Observe the under steps to unravel the issue:
- Initialize a variable depend = 0.
- Iterate a loop for every ingredient in A, and test if it is the same as the subsequent ingredient.
- If sure, increment the depend by 1.
- Print the depend which provides the minimal variety of operations required to make consecutive components totally different in an array.
Beneath is the implementation of the above strategy.
Java
|
|
Time Complexity: O(N)
Auxiliary Area: O(1)
