Найдите индекс, по которому должен быть установлен бит, чтобы максимизировать расстояние между следующим установленным битом

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

Примеры

Input: arr = [1, 0, 0, 0, 1, 0, 1]
Output: 2
Explanation: Flip the bit at arr[2]
 

Input: arr = [1, 0, 0, 0]
Output: 3

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

• Для всех расстояний между соседними заданными битами найти максимальное и сохранить его половину как один из искомых ответов.
• Затем найдите расстояние между расстоянием между 0 и первым установленным битом, а также между индексом N-1 и последним установленным битом.
• Найдите общий максимум как требуемый ответ.
• Выведите найденный ответ в конце.

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

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