Минимальные свопы для группировки всех нулей вместе в двоичном круговом массиве

Учитывая двоичный круговой массив arr[] размера N , задача состоит в том, чтобы найти минимальные перестановки , чтобы сгруппировать все 0 вместе в массиве.

Примеры :

Input: arr[] = {1, 0, 1, 0, 0, 1, 1}
Output: 1
Explanation: Here are a few of the ways to group all the 0’s together:

1. {1, 1, 0, 0, 0, 1, 1} using 1 swap.
2. {1, 0, 0, 0, 1, 1, 1} using 1 swap.
3. {0, 0, 1, 1, 1, 1, 0} using 2 swaps (using the circular property of the array).

There is no way to group all 0’s together with 0 swaps. Thus, the minimum number of swaps required is 1.

Input: arr[] = {0, 0, 1, 1, 0}
Output: 0
Explanation: All the 0’s are already grouped together due to the circular property of the array. 
Thus, the minimum number of swaps required is 0.

Подход: Задачу можно решить с помощью техники скользящего окна. Выполните следующие шаги, чтобы решить проблему:

• Подсчитайте общее количество 0s. Пусть m будет этим числом
• Найдите непрерывную область длины m , в которой больше всего нулей .
• Количество единиц в этой области является минимально необходимым свопом. Каждый обмен будет перемещать один 0 в регион и один 1 из региона.
• Наконец, используйте операцию по модулю для обработки случая круговых массивов.

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

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