Разбор задачи про бесконечный поезд

Даже если вы уже знаете решение этой распространенной на собеседованиях задачи, я на 95% уверен, что вы знаете популярное, но неоптимальное решение.

Хотите удивить интервьюера оптимальным решением? Тогда давайте разбираться. Звучит задача так:

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

Все вагоны внутри выглядят строго одинаково, окна закрыты так, что невозможно посмотреть наружу, движение поезда равномерное. Помечать вагоны как-либо, кроме включения или выключения света, нельзя. Количество вагонов конечно (не верьте заголовку).

Как посчитать количество вагонов?

Если видите задачу впервые, то попробуйте сначала решить ее сами.

А популярный алгоритм решения заключается в следующем:

Пусть в стартовом вагоне включен свет (иначе решаем от обратного):

1. Идём от стартового вагона в одном направлении и считаем шаги, пока не попадём в вагон со включённым светом.

2. В этом вагоне выключаем свет.

3. Возвращаемся назад ровно на столько шагов, сколько прошли вперёд.

4. Проверяем свет в стартовом вагоне. Если он выключен, значит мы случайно погасили именно стартовый вагон, и пройденное число шагов – это и есть число вагонов. Если включён, повторяем процесс.

По этой ссылке можно найти мой шортс с визуальным объяснением решения.

Но у такого решения есть нюанс. Если подойти к этой задаче не как к логической, а как к алгоритмической, то алгоритмическая сложность решения в худшем случае будет ~O(n^2) . Есть много схожих решений с микрооптимизациями, но порядок сложности они не меняют.

Можно ли решить задачу за линейную O(n) сложность? Сначала также подумайте сами.

А идея решения такая:

1. Включаем свет в стартовом вагоне.

2. Начинаем ходить влево и вправо на отрезки длиной 1, 2, 4, 8, 16, 2^N вагонов. При каждом проходе во всех вагонах слева от стартового включаем свет, а во всех вагонах справа от стартового – выключаем.

В какой-то момент отрезки слева и справа пересекутся: мы окажемся в вагоне, где ожидался уже включенный или выключенный свет, а в реальности окажется наоборот.

Это значит, что круг вагонов замкнулся в этой точке, и мы нашли точное число вагонов.

В комментариях к посту прикрепил визуальный пример.

Итоговое решение имеет линейную сложность. Вуаля