Задача из Яндекса

Дается массив из 0 и 1. Ваша задача выбрать такую позицию нуля, чтобы минимальное расстояние до единицы было максимальным.
Например 100110001
ответом будет позиция 6. 100110001. В задаче нельзя использовать дополнительную память, то есть можете использовать только О(1) дополнительной памяти.

Решение:
Очевидно, что если массив начинается с нуля то претендент на ответ это позиция 0.
Аналогично если массива заканчивается на 0 то претендент на ответ это позиция n - 1.
Теперь разберемся с остальными кейсами,пусть i1, i2, ,..., ik позиции где стоят единички, тогда очевидно претендентом на ответ будет нолик по середине между двумя соседними единицами, например в случае 1000001 ответом будет ноль по середине 1000001.

С идеей разобрались, теперь мы должны подумать как найти ответ без дополнительной памяти.
Конечно если бы знали ближайший слева и ближайший справа единичку для каждой позиции i то смогли бы очень просто решить задачу, но чтобы знать ближайший слева или ближайший справа единичку нам нужно создать дополнительный массив.....

Давайте хранить переменную last_one -которая будет хранить ближайший слева позицию единички от позиции i. (i - цикл по которому идем слева направо)
Если a[i] == 1 то есть встретили единичку, то мы понимаем что до этого единичка была в позиции last_one и нам выгоднее всего выбрать позицию (i + last_one) // 2 (конечно если там ноль)
Таким образом мы смогли решить задачу без дополнительной памяти.
Время работы алгоритма O(n)

Код в комментариях: