Тут можно заметить вот что.
1) если идем вверх, то обратный путь будет по тем же этажам:
туда 12-23-46, обратно 46-23-12
2) если идем вниз, то обратный путь может пойти по другим этажам:
туда 12-6, обратно 6-11-22-43
итого, решение простое - тебе сначала надо пройти от 12 вверх
потом от 12 спуститься до 6 и пройти вверх
потом от 6 спуститься до 3 и тоже пройти вверх (здесь выходим на предыдущий стартовый этаж 6, завершаем)
от 3 к 2 и тоже вверх
и т.д.
т.е. каждый раз спускаться вниз на одну, после чего идти вверх, если не попали на предыдущий стартовый.
код на js
function floorCount(start, max) {
let result = 0;
let prevStart = -1;
while (start > 0) {
for (let x = start; x <= max && x !== prevStart; x = x % 2 ? 2 * x : 2 * x - 1) {
result++;
}
prevStart = start;
start = start < 2 ? 0 : start % 2 ? (start + 1) / 2 : start / 2;
}
return result;
}
Это совсем частный случай ранее упомянутого поиска в ширину/глубину, где не понадобилось множество ранее посещенных этажей (достаточно проверки на prevStart), а так же очереди/стека. То есть обошлись О(1) памяти.
По скорости выходит O(ln(start) * ln(max)), и в принципе можно сократить до O(ln(start)), если не делать внутренний цикл, а сразу посчитать по формуле, но что-то на ночь глядя не могу эту формулу смекнуть...
