Минимизируйте вставку 0 или 1, чтобы ни одна соседняя пара не имела одинакового значения

Для заданного двоичного массива A[] длины N задача состоит в том, чтобы найти минимальное количество требуемых операций, чтобы ни одна соседняя пара не имела одинаковое значение, где в каждой операции мы можем вставить либо 0, либо 1 в любую позицию в массиве.

Примеры:

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 

Подход: Задача может быть решена на основе следующего наблюдения:

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 A_i = A_{i + 1}, which can be computed with a simple for loop.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную count = 0 .
• Повторите цикл для каждого элемента в A и проверьте, равен ли он следующему элементу.
  • Если да, увеличьте счетчик на 1.
• Выведите число, которое дает минимальное количество операций, необходимых для того, чтобы сделать последовательные элементы массива разными.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)