По поводу задачи о петле:
а) Начало правильное, но я еще не видел где координата за линейное время?
б) Гост: линейной дополнительной памяти никто не давал
Мне (и не тол'ко мне) нравится этот паттерн: 2 пойнтера движушиеся с разной скоростью --- он иногда красиво применим в разных задачах, помню что были, но не помню деталей...
в) Есть еще одно решение этой части задачи... кто найдет?