Найдите, удаляется ли 0 больше или 1, удаляя средний элемент, если последовательный триплет делится на 3 в данном двоичном массиве

Дан двоичный массив a[] размера N из 1 и 0 . Задача состоит в том, чтобы удалить элемент, если a[i-1]+a[i]+a[i+1] делится на 3 . Выведите 1 , если удалено больше единиц, чем 0 , иначе выведите 0 .

Примеры:

Input: a[] = { 1, 1, 1, 0, 1, 0, 0}
Output: 1
Explanation: Remove the second 1 from the left since that is the only ‘1’ for which (a[i]+a[i-1]+a[i+1]) %3==0. So print 1.

Input: a[] = { 1, 1}
Output: 0 
Explanation: No removal possible, so print 0.

Подход: Идея основана на наблюдении, что если оба соседа равны текущему элементу, потому что если (a[i]=a[i-1]=a[i+1]) , то сумма всегда будет делиться на 3 . Допустим, A хранит количество удаленных единиц, а B хранит количество удаленных нулей . Если i -й элемент равен соседям, то если a[i] =1 , увеличить A , иначе B . Если количество A больше, чем B , выведите 1 , иначе выведите 2=0 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные A и B как 0 , чтобы сохранить количество удаленных 1 и 0 .
• Переберите диапазон [0, N), используя переменную i , и выполните следующие шаги:
  • Если a[i-1], a[i] и a[i+1] равны, то если a[i] равно 1, то увеличьте значение A на 1 , иначе B на 1.
• Если A больше B, то выведите 1 , иначе выведите 0.

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

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