Условие

Дано кольцевое шоссе с n остановками, расстояние между которыми задано массивом distance, где distance[i] — расстояние между остановками i и (i + 1) % n. Нужно найти минимальное расстояние между остановками start и destination.

Примеры

Input: distance = [1, 2, 3, 4], start = 0, destination = 1 Output: 1 Explanation: Единственный маршрут — от остановки 0 до 1, расстояние 1.

Input: distance = [1, 2, 3, 4], start = 0, destination = 2 Output: 2 Explanation: По часовой стрелке: 1 + 2 = 3. Против часовой стрелки: 4, минимальное расстояние — 3.

Input: distance = [1, 2, 3, 4], start = 0, destination = 3 Output: 3 Explanation: По часовой стрелке: 1 + 2 + 3 = 6. Против часовой стрелки: 4, минимальное расстояние — 4.

Решение

fun distanceBetweenBusStops(distance: IntArray, start: Int, destination: Int): Int {
    // Определяем меньший и больший индекс
    var min = start
    var max = destination
    if (min > max) {
        val temp = min
        min = max
        max = temp
    }

    var direct = 0   // Сумма расстояний по часовой стрелке
    var total = 0    // Общее расстояние по кругу

    for (i in distance.indices) {
        total += distance[i] // Считаем общее расстояние
        if (i in min until max) {
            direct += distance[i] // Считаем расстояние в прямом направлении
        }
    }

    // Выбираем минимальное расстояние между прямым и обратным маршрутом
    return if (direct < total - direct) direct else total - direct
}

Временная сложность

O(n), где n — количество остановок.

Пространственная сложность

O(1), так как используются только несколько переменных.